[SWEA] 1226_미로1

📕 문제

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.
가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.
주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.
아래의 예시에서는 도달 가능하다.

 아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트케이스가 주어진다.
테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

 

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

 

💡 풀이법

1. 미로에서 시작점(2)을 찾아서 시작점의 인덱스로 시작을 한다.

2. 사방을 보며 벽이 아니면서 통로(0)인 좌표를 찾고  q라는 리스트에 넣는다.

3. 만약 사방을 보다가 3을 찾으면 그때 1을 return.

 

def bfs(y, x):
    q = [(y, x)]
    dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 오른쪽, 아래, 왼쪽, 위

    while q:
        y, x = q.pop(0)
        if maze[y][x] == 0 or 2:
            maze[y][x] = 1

            for dy, dx in dxy:
                ny, nx = y + dy, x + dx

                if 0 <= ny <= 15 and 0 <= nx <= 15:
                    if maze[ny][nx] == 0:
                        q.append((ny, nx))
                    elif maze[ny][nx] == 3:
                        return 1
    return 0

for _ in range(10):
    T = int(input())
    maze = [list(map(int,list(input()))) for _ in range(16)]
    for i in range(16):
        if 2 in maze[i]:
            sy, sx = i, maze[i].index(2)
            break
    print('#{} {}'.format(T, bfs(sy, sx)))

-> 이제 점점 dfs와 bfs가 익숙해지고 있다😀