문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

www.acmicpc.net/problem/4179

  • 입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이 난 공간

J는 입력에서 하나만 주어진다.

  • 출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

최종 코드

불과 지훈에 대해서 각각, 그리고 또 동시에 bfs를 사용해야 한다는 것 까지는 문제를 보고 이해했다. 하지만 bfs 알고리즘에 대한 구현 경험이 거의 없어서 구현할 수가 없었다ㅠㅠ. 스터디를 위해서라도 기본 문제부터 얼른 풀어서 실력을 쌓아가고 싶다. 스터디 하시는 분들이 다들 나보다 똑똑해서 그분들의 코드를 통해 많이 배울 수 있었다.

두 가지 방법으로 코드를 구현해보았다. 우선 첫 번째는 지훈과 불을 동시에 bfs를 돌리는데, 지훈 -> 불 순서로 가는 것이다. 여기서는 maze 배열 하나만으로 문제를 해결할 수 있었다(내가 참고한 코드에서는 visit 배열을 하나 더 만들어 사용했지만 구현하다보니 필요가 없다는 것을 깨달았다).

또한 bfs를 동시에 돌리기 위한 방법으로 temp(deque)를 사용했다. pop은 원래 큐에서 진행하되, append는 임시로 temp에 해놓고 큐가 빌 때까지 while문을 돌리는 것이다. 그리고 while문이 끝나면 temp 내용을 원래 큐에 옮긴다.

from collections import deque

def bfs():
    global maze, jq, fq
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 지훈->불 순서로 동시에 bfs를 돌림
    while jq:
        temp = deque()
        # 지훈 bfs
        while jq:
            x, y = jq.popleft()
            # 마지막 행/열에 도착했을 때 maze[x][y]가 불이 아니라면 탈출 가능
            if (x == r-1 or y == c-1 or x == 0 or y == 0) and maze[x][y] != 'F':
                return maze[x][y]
            # maze[x][y] 위치에 불이 번졌다면 이 위치로는 이동 불가
            elif maze[x][y] == 'F':
                continue

            # 상하좌우로 이동할 수 있는 곳을 탐색
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= r or ny >= c:
                    continue
                elif maze[nx][ny] == '.':
                    temp.append([nx, ny])
                    maze[nx][ny] = maze[x][y] + 1
        jq = temp
        # jq가 비어있어 더 이상 이동할 곳이 없다면 실패
        if not jq:
            break

        temp = deque()
        # 불 bfs
        while fq:
            x, y = fq.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= r or ny >= c:
                    continue
                elif maze[nx][ny] != '#' and maze[nx][ny] != 'F':
                    temp.append([nx, ny])
                    maze[nx][ny] = 'F'
        fq = temp
    return "IMPOSSIBLE"

# 행,열의 크기와 미로 입력 받기    
r, c = map(int, input().split())
maze = []
for i in range(r):
    maze.append(list(input()))

jq = deque()
fq = deque()

# 미로를 돌면서 지훈의 위치와 불의 위치(들)을 찾아 큐에 먼저 집어 넣기
for i in range(r):
    for j in range(c):
        if maze[i][j] == 'J':
            jq.append([i, j])
            maze[i][j] = 1
        elif maze[i][j] == 'F':
            fq.append([i, j])

print(bfs())

알고리즘은 거의 같지만 두 번째는 불 -> 지훈 순서로 bfs가 돌아가도록 구현했다. 이해하기에는 이게 더 직관적인 것 같다. 여기에서는 불의 번짐을 저장할 maze 배열과 지훈이 이동한 거리를 저장할 dist 배열 두 개를 사용했다.

또 bfs를 동시에 돌리기 위해서 큐의 크기를 이용했다. while문 전에 현재 큐의 크기를 저장해놓고, pop할 때마다 -1을 해준다. 그리고 저장한 큐의 크기가 0이 될 때 while을 나가는 방법이다.

from collections import deque

def bfs():
    global maze, jq, fq, dist
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 불->지훈 순서로 동시에 bfs를 돌림
    while jq:
        # 불 bfs
        fqlen = len(fq)
        while fqlen:
            x, y = fq.popleft()
            fqlen -= 1

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= r or ny >= c:
                    continue
                elif maze[nx][ny] == '.':
                    fq.append([nx, ny])
                    maze[nx][ny] = 'F'

        # 지훈 bfs
        jqlen = len(jq)
        while jqlen:
            x, y = jq.popleft()
            jqlen -= 1

            # 마지막 행/열에 도착했다면 탈출 가능
            if x == r-1 or y == c-1 or x == 0 or y == 0:
                return dist[x][y]

            # 상하좌우로 이동할 수 있는 곳을 탐색
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= r or ny >= c:
                    continue
                elif maze[nx][ny] == '.' and dist[nx][ny] == 0:
                    jq.append([nx, ny])
                    dist[nx][ny] = dist[x][y] + 1

    return "IMPOSSIBLE"

# 행,열의 크기와 미로 입력 받기    
r, c = map(int, input().split())
maze = []
for i in range(r):
    maze.append(list(input()))

jq = deque()
fq = deque()
dist = [[0]*c for _ in range(r)]

# 미로를 돌면서 지훈의 위치와 불의 위치(들)을 찾아 큐에 먼저 집어 넣기
for i in range(r):
    for j in range(c):
        if maze[i][j] == 'J':
            jq.append([i, j])
            maze[i][j] = '.'
            dist[i][j] = 1
        elif maze[i][j] == 'F':
            fq.append([i, j])

print(bfs())

참고 사이트