길 확인하기

문제 저작권상 간략하게 올린다.

(0, 0)에서 출발하여 (7, 7)로 도달할 수 있는가?

단, 0은 벽, 1은 좌우 이동 가능, 2는 상하 이동 가능, 3은 상우 이동 가능, 4는 좌하 이동 가능이다.

※ 알게된 것

2차원 격자에서 두 방향으로만 이동 가능한 이런 문제는 DFS/BFS를 굳이 안 써도, 

대부분 반복문만으로 해결 가능하다. (물론 우회나 퇴보는 불가능)

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int T = 0;
 
    int map[8][8] = { 0, };
    bool Check[8][8] = { false, };
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        memset(map, 0, sizeof(map));
        memset(Check, false, sizeof(Check));
 
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        Check[0][0] = true; // 출발점은 true
 
        // 오른쪽과 아래로만 이동하므로, 단순 2중 for문 가능
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                // 이번 칸이 도착지까지 도달 할 수 없는 칸이라면 고려할 필요 없다.
                if (!Check[i][j]) continue;
 
                if (map[i][j] == 1 || map[i][j] == 3) // 현재 있는 곳이 오른쪽으로 갈 수 있는 곳이라면
                {
                    if (j + 1 < 8 && (map[i][j + 1] == 1 || map[i][j + 1] == 4))
                    {
                        // (다음 칸 기준) 다음 칸이 왼쪽에서 들어올 수 있는 칸이라면
                        Check[i][j + 1] = true;
                    }
                }
                else if (map[i][j] == 2 || map[i][j] == 4) // 현재 있는 곳이 아래로 내려갈 수 있는 곳이라면
                {
                    if (i + 1 < 8 && (map[i + 1][j] == 2 || map[i + 1][j] == 3))
                    {
                        // 아래에 있는 칸 기준으로 아래 칸이 위쪽에서 들어올 수 있는 칸이라면
                        Check[i + 1][j] = true;
                    }
                }
            }
        }
 
        if (Check[7][7]) printf("YES\n");
        else printf("NO\n");
    }
 
    return 0;
}