[C++] SWEA 1210번: Ladder1

🔗 문제

SW Expert Academy

SW Expert Academy

 

🖍 풀이

사다리 0행부터 따라 내려가지 않는다.

X부터 역으로 사다리를 거슬러 올라가 0행일 때의 answer열을 찾는 방법을 사용했다.

 

X의 위치를 destination이라는 좌표로 저장하였다.

사다리 타기 특성상 양옆으로 가는 길이 있다면 위가 아닌 옆으로만 가야 한다.

이를 위해 dx, dy에 좌,우,상 좌표를 넣고 먼저 매치되는 방향 하나로만 탐색해준다.

 

사다리 방향 전환을 하며 이동전 위치로 돌아가지 않도록 visited로 재방문 방지도 해주었다.

 

💾  소스

#include <iostream>
#include <queue>

int answer = 0;

const int dx[3] = {0, 0, -1};
const int dy[3] = {-1, 1, 0};

int map[101][101] = {0, };
bool visited[101][101] = {false, };

bool isValid(int x, int y)
{
    if(x<0 || y<0 || x>=100 || y>=100)
        return false;
    
    return true;
}

void DFS(const int r, const int c)
{
    if(r == 0)
    {
        answer = c;
        return;
    }
    
    for(int d=0; d<3; ++d)
    {
        int x = r + dx[d];
        int y = c + dy[d];
        
        if(isValid(x, y) && map[x][y]!=0 && !visited[x][y])
        {
            visited[x][y] = true;
            DFS(x, y);
            return;
        }
    }
}

int main()
{
    int T = 10; //std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {
				std::pair<int, int> destination;
        std::cin >> answer;
        for(int i=0; i<100; ++i)
        {
            for(int j=0; j<100; ++j)
            {
                std::cin >> map[i][j];
                visited[i][j]= false; // 초기화
                if(map[i][j]==2)
                {
                    destination = std::make_pair(i, j);
                }
                
            }
        }
        
        visited[destination.first][destination.second] = true;
        DFS(destination.first, destination.second);

        std::cout << '#' << tc << ' ' << answer << '\\n';
    }
    return 0;
}