전형적인 BFS(너비 우선 탐색)의 문제이다.
상근이는 불이 있는 쪽으로 가지 못하지만 불이 다가 오기 전 먼저 외각쪽으로 다가가면 탈출한다.
따라서 상근이의 위치를 먼저 큐에 넣어주고 BFS를 돌린다.
pypy로 제출
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def spread(q):
while q:
x, y, type, cnt = q.popleft()
for dir in range(4):
nx, ny = x + dx[dir], y + dy[dir]
if type == '@' and graph[x][y] == '*':
continue
if type == '@' and (nx < 0 or ny < 0 or nx >= row or ny >= col):
result.append(cnt)
return cnt + 1
if nx < 0 or ny < 0 or nx >= row or ny >= col or graph[nx][ny] == '#':
continue
if type == '@' and graph[nx][ny] != '.':
continue
if type == '*' and graph[nx][ny] == '*':
continue
visited[nx][ny] = 1
graph[nx][ny] = type
q.append((nx, ny, type, cnt + 1))
return -1
def BFS(q):
result = spread(q)
if result == -1:
print("IMPOSSIBLE")
else:
print(result)
test_case = int(input())
for _ in range(test_case):
col, row = map(int, input().split())
graph = [list(input()) for _ in range(row)]
visited = [[0 for _ in range(col)] for _ in range(row)]
q = deque()
result = []
for r in range(row):
for c in range(col):
if graph[r][c] == '@':
q.append((r, c, '@', 0))
visited[r][c] = 1
for r in range(row):
for c in range(col):
if graph[r][c] == '*':
q.append((r, c, '*', 0))
visited[r][c] = 1
BFS(q)
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def spread(q):
while q:
x, y, type, cnt = q.popleft()
for dir in range(4):
nx, ny = x + dx[dir], y + dy[dir]
if type == 'J' and graph[x][y] == '*':
continue
if type == 'J' and (nx < 0 or ny < 0 or nx >= row or ny >= col):
result.append(cnt)
return cnt
if nx < 0 or ny < 0 or nx >= row or ny >= col or graph[nx][ny] == '#':
continue
if type == 'J' and graph[nx][ny] != '.':
continue
if type == 'F' and graph[nx][ny] == 'F':
continue
visited[nx][ny] = 1
graph[nx][ny] = type
q.append((nx, ny, type, cnt + 1))
return -1
def BFS(q):
result = spread(q)
if result == -1:
print("IMPOSSIBLE")
else:
print(result + 1)
row, col = map(int, input().split())
graph = [list(input()) for _ in range(row)]
visited = [[0 for _ in range(col)] for _ in range(row)]
q = deque()
result = []
for r in range(row):
for c in range(col):
if graph[r][c] == 'F':
q.append((r, c, 'F', 0))
visited[r][c] = 1
for r in range(row):
for c in range(col):
if graph[r][c] == 'J':
q.append((r, c, 'J', 0))
visited[r][c] = 1
BFS(q)위의 불과 비슷한 문제다.
차이점이 있다면 위의 문제는 상근이를 먼저 큐에 넣었지만, 여기선 불을 먼저 넣어야 통과가 된다.
