4179번 - 불!

💡 bfs 문제 중 정말 어려웠던 문제였다.. 풀이법을 빠르게 생각하는 것이 중요하다!

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split(' '))

graph = [list(input().rstrip()) for _ in range(R)]

# 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

dq = deque()
jihun_x, jihun_y = 0, 0

# 불 위치 저장
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            jihun_x , jihun_y = j, i
        elif graph[i][j] == 'F':
            dq.append((j,i, 'F', 0))

# 지훈 위치 저장
dq.append((jihun_x,jihun_y,'J', 0)) 

def bfs():
    
    cnt = 0
    
    while dq:
        x, y, val, cnt = dq.popleft()
        
        if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
            return cnt + 1
                
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            
            if val == 'J':
                if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
                    graph[ny][nx] = 'J'
                    dq.append((nx,ny,'J', cnt + 1))
            else:
                if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
                    graph[ny][nx] = 'F'
                    dq.append((nx,ny,'F', 0))
    
    return "IMPOSSIBLE"
                    
print(bfs())

• 이번 문제는 정말 오래걸렸고, 결국은 스터디에서 hint를 얻어서 풀게 되었다.
• 삽질을 정말 많이 했고, 간단하게 삽질해봤던 부분들을 정리해보겠다.
  1) visited 배열을 사용해서 visited가 False,True로 체크하는 과정을 거쳤다 - 필요 X
  2) cnt를 두고, 'J'일 경우에는 cnt += 1로 매번 경우의 수를 업데이트 하였다. - X
  ( 이 부분은 결국 최솟값을 구해야 하고, 모든 경로의 J의 경우 수를 전부 구하는 거여서 옳지 않다.)
  3) 불보다 지훈을 먼저 dq에 추가하였다. - X
  ( Jihun이 갈 수 있는 가장 최소의 경로로 진행하려면 불의 경로를 먼저 진행해야한다.)

< 핵심 코드 >

1) 불, Jihun 저장 코드

dq = deque()
jihun_x, jihun_y = 0, 0

# 불 위치 저장
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            jihun_x , jihun_y = j, i
        elif graph[i][j] == 'F':
            dq.append((j,i, 'F', 0))

# 지훈 위치 저장
dq.append((jihun_x,jihun_y,'J', 0)) 

• jihun은 전체에서 1번밖에 없기 때문에, 해당 위치를 jihun_x, jihun_y에 저장한다.
• 불의 위치를 jihun보다 먼저 저장해야 하기 때문에, dq에 불에 대한 정보를 추가해준다.
  ( 불의 정보는 x위치, y위치, Fire/Jihun, 갯수 로 이루어져 있다.)
  ( 여기서 갯수가 추가된 것은 경로를 진행할 때마다, 경로가 1씩 증가해줘야 하기 떄문에)
• 불의 위치를 저장하고 나서, 지훈의 위치에 대한 정보를 dq에 추가해준다.

2) 종료 조건

if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
	return cnt + 1

• dq의 맨 앞부분의 val이 J라면, (즉, Jihun이라면) cnt + 1값을 return 해주면서 종료한다.

3) dq에서 Fire와 Jihun 처리

if val == 'J':
	if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
		graph[ny][nx] = 'J'
		dq.append((nx,ny,'J', cnt + 1))
else:
	if 0 <= nx < C and 0 <= ny < R and graph[ny][nx] == '.':
		graph[ny][nx] = 'F'
		dq.append((nx,ny,'F', 0))

• graph의 값을 J로 바꿔주면서, visited 배열을 대체하였다.
• Fire의 경우에는 불이 번지면 불의 공간이 고정이기 떄문에, graph의 값을 변경해주었다.
• 범주내에 포함되며, graph값이 .이여서 확장 가능하면 Jihun일 경우에는 해당 경로로 이동해주고, cnt를 1씩 더해주었다.

4) 조건 만족시 return과 만족 아닐 시 return

while dq:

  if val == 'J' and (x == 0 or x == C-1 or y == 0 or y == R-1):
      return cnt + 1

( 생략 )
    
return "IMPOSSIBLE"

• J가 범주에 만족하게 되면, 탈출하고 return 해주었다.
• 범주에 만족하지 못하고, 결국 dq가 다 비게 되면 IMPOSSIBLE을 return 해주었다.
  ( 결국 범주에 포함되지 못하면, #이나 F에 가로 막혔다는 것을 의미한다.)

💡 코테스터디에서 나온 기발한 접근법

import sys
from collections import deque

input = sys.stdin.readline
r, c = map(int, input().split())
graph = []

q_j = deque()
q_f = deque()

visited_j = [[0] * c for _ in range(r)]
visited_f = [[0] * c for _ in range(r)]

move = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
]

for i in range(r):
    temp = list(input())

    for j in range(len(temp)):
        if temp[j] == "J":
            q_j.append((i, j))
            visited_j[i][j] = 1
        
        elif temp[j] == "F":
            q_f.append((i, j))
            visited_f[i][j] = 1
        
    graph.append(temp)

def bfs():
    while q_f:
        x, y = q_f.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if not visited_f[nx][ny] and graph[nx][ny] != "#":
                    visited_f[nx][ny] = visited_f[x][y] + 1
                    q_f.append((nx, ny))

    while q_j:
        x, y = q_j.popleft()

        for i in range(4):
            nx, ny = x + move[i][0], y + move[i][1]

            if 0 <= nx < r and 0 <= ny < c:
                if graph[nx][ny] != "#" and not visited_j[nx][ny]:
                    if not visited_f[nx][ny] or visited_f[nx][ny] > visited_j[x][y] + 1:
                        visited_j[nx][ny] = visited_j[x][y] + 1
                        q_j.append((nx, ny))

            else:
                return visited_j[x][y]

    
    return "IMPOSSIBLE"

print(bfs())

• visited 배열을 jihun용, fire용으로 따로 두어서 진행하였다.
• fire의 경우에는 이전 visited 배열의 값에 +1을 해주면서, Fire가 번지는 일수를 같이 표현해줘서, fire가 번져나갈 수 있는 경우의 수를 먼저 진행한다.
• Jihun의 경우에는 확장하면서, .인 경우에는 자동으로 진행할 수 있고, 만약 F인 경우에는 Jihun의 visited값과 비교해서 Jihun이 작으면 확장하면서 변환해준다.
  ( Fire의 visited가 jihun이 확장되는 visited보다 크다면, Fire가 확장되기 전에 Jihun이 해당하는 부분에 도달했다라는 의미이기 떄문에 확장이 가능하다.)