[SWEA] 미로의 거리

[SWEA] 미로의 거리

Problem URL : 미로의 거리

d = [[1, 0], [0, 1], [-1, 0], [0, -1]]

TC = int(input())
for tc in range(1, TC + 1):
    N = int(input())
    arr = [list(map(int, input())) for _ in range(N)]
    visit = [[-1] * N for _ in range(N)]
    q = []
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 2:
                q.append((i, j))
                visit[i][j] = 0
                break
        if q:
            break

    ans = 0

    while q:
        now = q.pop(0)
        x = now[0]
        y = now[1]

        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] != 1 and visit[nx][ny] == -1:
                if arr[nx][ny] == 3:
                    ans = visit[x][y]
                    break
                visit[nx][ny] = visit[x][y] + 1
                q.append((nx, ny))

        if ans:
            break

    print('#{} {}'.format(tc, ans))

Comments

간단한 BFS 문제