SWE(5105)_미로의거리

작성일 | In

SWE 5105 미로의 거리

  • NxN 크기의 미로에서 출발지 목적지가 주어진다,
  • 이 때, 최소 몇 개의 칸을 지나면, 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램 작성

  • 1은 벽, 0은 통로, 미로 밖으로 벗어나서는 안된다.

  • SWEA 4875 미로와 동일한 문제지만, SWEA에서는 4875에서는 BFS를 적용했다.
  • 이 문제는 BFS 적용해서 풀어보자
def IsSafe(y, x):
    return 0 <= y < N and 0 <= x < N and (Maze[y][x] == 0 or Maze[y][x] == 3)

def BFS(start_y, start_x):
    global D_result
    Q.append((start_y, start_x))
    visited.append((start_y, start_x))

    while Q:
        start_y, start_x = Q.pop(0)
        for dir in range(4):
            NewY = start_y + dy[dir]
            NewX = start_x + dx[dir]
            if IsSafe(NewY, NewX) and (NewY, NewX) not in visited:
                Q.append((NewY, NewX))
                visited.append((NewY, NewX))
                Distance[NewY][NewX] = Distance[start_y][start_x] + 1
                if Maze[NewY][NewX] == 3:
                    D_result = Distance[NewY][NewX] - 1
                    return

TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Maze = [list(map(int, input())) for _ in range(N)]
    visited = [[0]*N for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if Maze[y][x] == 2:
                start_y, start_x = y, x
    dy = [1, -1, 0, 0]
    dx = [0, 0, -1, 1]

    D_result = 0
    Q = []
    Distance = [[0]*N for _ in range(N)]
    BFS(start_y, start_x)
    print(f'#{tc} {D_result}')

참고자료 [SWexperacademy]https://swexpertacademy.com

0%