[DFS/BFS/완전탐색] ★★ 4179번 - 불!(BFS)

[백준] 4179번 - 불!

풀이 시간: 6시간 이내

유사한 문제: 3055

https://hseungyeon.tistory.com/241

[DFS/BFS/완전탐색] 3055번 - 탈출(BFS)

 

(풀이1) 실패한 코드

1) 문제 해결 아이디어

많이 어려웠던 문제로 추후 복습이 꼭 필요!

미로에서 지훈이의 위치와 불의 위치가 주어진다. 1분마다 지훈이는 상하좌우 중 1 방향으로 한 칸씩 이동하고 불은 상하좌우 4방향으로 1칸씩 이동한다. 지훈이가 불이 도달하기 전에 미로를 탈출 할 수 있는 최소 시간을 구하는 문제로 BFS로 풀이가 가능하다.

사실 이 문제는 이전에 업로드했던 3055번과 본질적으로 완전 똑같은 문제다. 원래 이 문제를 먼저 풀었었는데 도저히 다른 풀이를 봐도 이해가 가지 않아 3055번을 먼저 풀다가 결국 해결을 하고 업로드를 했다.

 

이 문제가 어려웠던 이유는 다른 BFS문제와 달리 1분마다 지훈, 불을 각각 이동시키고 결과를 확인해야했기 때문이다. 보통 문제들은 큐를 1개만 써서 구현했지만 여기서는 지훈, 불을 구분해줘야할 필요가 있기 때문에 지훈이를 위한 큐(queueJ), 불을 위한 큐(queueF) 이렇게 2개를 생성했다.

 

첫번째 오류. 메모리 초과

 

 

2) 소스코드

from collections import deque
import sys


# BFS
def bfs(x, y, state):
  queue = deque()
  # 시작점 삽입, 방문 처리
  queue.append((x, y))
  visited[x][y] = 0

  # 상태가 불이면
  if(state == 'F'):  
    while queue:
      x, y = queue.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if(0 <= nx < r and 0 <= ny < c):
          # 벽이 아니고 방문한적이 없으면 삽입, 방문 처리
          if(result[nx][ny] != '#' and visited[nx][ny] == 0):
            queue.append((nx, ny))
            visited[nx][ny] = 1
            result[nx][ny] = 'F'  # 불 번짐
  # 상태가 지훈이면
  elif(state == 'J'):  
    while queue:
      x, y = queue.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if(0 <= nx < r and 0 <= ny < c):
          # 길이고 방문한적이 없으면 삽입, 방문 처리
          if(result[nx][ny] == '.' and visited[nx][ny] == 0):
            queue.append((nx, ny))
            visited[nx][ny] = 1
            result[nx][ny] = 'J'  # 지훈 이동


r, c = map(int, input().split())  # 세로, 가로
# r*c (#: 벽, .: 길, J: 초기 위치, F: 불이 난 곳)
graph = [list(input()) for _ in range(r)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

jLoc = [0, 0]  # 지훈 위치
# 지훈 위치 찾기
for i in range(r):
  for j in range(c):
    if(graph[i][j] == 'J'):
      jLoc = [i, j]  # 지훈 위치

time = 0
while True:
  visited = [[0] * c for _ in range(r)]
  result = list(graph)

  # 지훈 이동
  for i in range(r):
    for j in range(c):
      # 불이면 
      if(graph[i][j] == 'J'): 
        bfs(i, j, "J")
  # 불 이동
  for i in range(r):
    for j in range(c):
      # 불이면 
      if(graph[i][j] == 'F'): 
        bfs(i, j, "F")

  for i in graph:
    print(i)
  break
  time += 1

 

(풀이2) 성공한 코드

1) 문제 해결 아이디어

자세한 풀이는 3055번 풀이글을 참고하자. (이해를 돕기위해 이 문제에서 지훈, 불, 벽이 3055번의 무엇에 대응하는지를 확인하자)

지훈 = 고슴도치

불 = 물

벽 = 돌

 

이 문제에서도 지훈→불 순으로 이동시키게 코드를 짰다.

 

<지훈 이동 조건>

1. 빈 곳(.)

 

<불 이동 조건>

1. 빈 곳(.)

2. 지훈이가 이미 지나갔던 곳(숫자)

 

<지훈 탈출 성공 조건>

지훈 위치 큐(queueJ)에서 꺼낸 좌표(x, y)의 상하좌우 칸이 범위를 벗어나면 탈출 성공이므로 꺼낸 좌표의 값 + 1(graph[x][y] + 1)을 리턴

 

<지훈 탈출 실패 조건>

지훈 위치 큐(queueJ)에서 더이상 꺼낼 좌표(x, y)가 없으면 탈출 실패로 "IMPOSSIBLE" 리턴

 

2) 소스코드

from collections import deque
import sys
input = sys.stdin.readline

# BFS
def bfs():
  while True:
    # 1. 지훈 1분 이동
    for i in range(len(queueJ)):
      x, y = queueJ.popleft()
      # 꺼낸 지훈의 위치값이 불(F)로 덮어쓰여졌다면 건너뛰기
      if(graph[x][y] == 'F'): continue
      for j in range(4):
        nx = x + dx[j]
        ny = y + dy[j]
        # 범위 내이고
        if(0 <= nx < r and 0 <= ny < c):
          # 빈 곳이면 삽입, 방문 처리
          if(graph[nx][ny] == '.'):
            queueJ.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1
        # 범위 밖이면 탈출
        else: return graph[x][y] + 1
    # 2. 불 1분 이동
    for i in range(len(queueF)):
      x, y = queueF.popleft()
      for j in range(4):
        nx = x + dx[j]
        ny = y + dy[j]
        # 범위 내이고
        if(0 <= nx < r and 0 <= ny < c):
          # 빈 곳 혹은 지훈이 지나간 곳(숫자)이면 삽입, 방문 처리
          if(graph[nx][ny] == '.' or type(graph[nx][ny]) == int):
            queueF.append((nx, ny))
            graph[nx][ny] = 'F'
    # 더이상 꺼낼 지훈의 좌표가 없다면
    if not queueJ:  return "IMPOSSIBLE"
          
      



r, c = map(int, input().split())  # 세로, 가로
# r*c (.: 빈곳, #: 벽, J: 지훈, F: 불)
graph = [list(input().strip()) for _ in range(r)]
queueJ = deque()  # 지훈 위치를 담을 큐
queueF = deque()  # 불 위치를 담을 큐
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 지훈, 불 시작점 위치 찾기
for i in range(r):
  for j in range(c):
    # 지훈이면 삽입, 방문 처리
    if(graph[i][j] == 'J'):
      queueJ.append((i, j))
      graph[i][j] = 0
    # 불이면 삽입(방문처리는 따로 할 필요X)
    elif(graph[i][j] == 'F'):
      queueF.append((i, j))
print(bfs())