2일차 - Ladder2

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV14BgD6AEECFAYh&categoryId=AV14BgD6AEECFAYh&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=2
이문제 2시간넘게 왜틀린지 모르겟음.
10X10배열에서 내가 인풋 넣은건 이상없으나,
그이상 진행이 되지 않음...
답이 다르게 나온다.
백트래킹으로 다시 풀어봐야 한다
디버깅 할때 100x100으로 해야되는데 cmd창에 올라가질 않는다...
일단 실패했음.

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int arr[100][100] = { 0, };
int visit[100][100] = { 0, };
int dx[3] = { 1,-1,0 };//기본 우-> 좌 -> 밑으로
int dy[3] = { 0,0,1 };

typedef struct {
    int x;
    int xpath_Cnt;
}max_struct;

vector<max_struct> vTemp;

int answer;

void  bfs(int y, int x)
{
    int path_length = 1;
    queue<pair<int, int>> qTemp;
    qTemp.push(make_pair(y, x));//
    visit[y][x] = 1;
    while (!qTemp.empty())
    {
        int iTempy = qTemp.front().first;
        int iTempx = qTemp.front().second;
        qTemp.pop();
        for (int i = 0; i < 3; i++)
        {
            int ny = iTempy+dy[i];
            int nx = iTempx+dx[i];
            if (ny >= 0 && ny < 100 && nx >= 0 && nx < 100)//기본 사각 바운더리
            {
                if (ny == 99 && arr[ny][nx] == 1)
                {
                    max_struct mxTempStruct;
                    mxTempStruct.x = x;
                    mxTempStruct.xpath_Cnt = path_length;
                    vTemp.emplace_back(mxTempStruct);
                    return;
                }

                if ((arr[ny][nx] == 1 && visit[ny][nx] == 0))//0이고 방문 안했으면
                {
                    visit[ny][nx] = 1;
                    qTemp.push(make_pair(ny, nx));
                    path_length++;
                    break; //이 break를 통해 우 좌 하강에서 여러개 안하고 그냥 하나만한다. 
                }
            }
        }
    }

    return ;
}

void clear_all()
{
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            arr[i][j] = 0;
            visit[i][j] = 0;
        }
    }
    vTemp.clear();
    answer = 0;
}

void clear_visit()
{
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            visit[i][j] = 0;
        }
    }
}

int main() {

    int test_case;

    for (test_case = 0; test_case < 10; test_case++) 
    {
        clear_all();

        int iCnt(0);
         cin >> iCnt;


         for (int i = 0; i < 100; i++)
         {
             for (int j = 0; j < 100; j++)
             {
                 cin >> arr[i][j];
             }
         }

      
         for (int i = 0; i < 100; i++)
         {
             if (arr[0][i] == 1)
             {
                 bfs(0, i);
                 clear_visit();
             }
         }
     
         sort(vTemp.begin(), vTemp.end(), [](max_struct a, max_struct b) {
             if(a.xpath_Cnt == b.xpath_Cnt)
             {
                 return a.x > b.x;
             }
             else
             {
                 return a.xpath_Cnt > b.xpath_Cnt;
             }
         });
     
        //출력
        cout << "#" << test_case+1 << " " << vTemp[0].x << endl;
    }

    //종료
    return 0;
}

좋은 웹페이지 즐겨찾기