[백준4179&파이썬] 불!/BFS를 이용해 조건에 맞는 최단거리를 구하는 방법

# 문제

백준 4179 불! 파이썬 풀이

4179번: 불!

 

# 코드

import sys
from collections import deque

R,C = map(int, sys.stdin.readline().split())



board = list()
visit = [ [False for j in range(C) ] for i in range(R) ]
j_flag = True
f_starting = list()
j_pos = [-1,-1]


for i in range(R) :
  line = list(sys.stdin.readline().strip())
  board.append(line)
  if j_flag :
    for j in range(C) :
      if line[j] == "J" :
        j_pos[0] = i; j_pos[1] = j;
        j_flag = False

  for j in range(C) :
    if line[j] == "F" :
      f_starting.append( (i,j) )


dq = deque()
for f in f_starting :
  dq.append((f[0],f[1],"F",1))

dq.append( (j_pos[0],j_pos[1],"J",1) )

dirs = [
  (-1,0),(0,1),(1,0),(0,-1)
  ]

while len(dq) !=0 :
  cur = dq.popleft()
  if cur[2] == "J":  # 지훈이일때
    if (cur[0] == 0 or cur[0] == R - 1) or (cur[1] == 0 or cur[1] == C - 1):  # 이동전에 그곳이 탈출 구 인지 확인함
      print(cur[3])  # 여기서 탈출
      # print(board)
      exit()

  for dir in dirs :
    next = ( cur[0] + dir[0], cur[1] + dir[1], cur[2], cur[3] +1 )
    if 0<= next[0] < R and 0<= next[1] < C :
      if cur[2] == "F" : # 불일때
        if (board[next[0]][next[1]] == "." or board[next[0]][next[1]] == "J") :
          # 다음칸으로 불 이동
          dq.append(next)
          board[next[0]][next[1]] = "F"

      if cur[2] == "J" : # 지훈이일때
        if board[next[0]][next[1]] == "." : # 불이 안간 곳이면서 다음이 이동 가능할때

          if (next[0] == 0 or next[0] == R-1 ) or (next[1] == 0 or next[1] == C-1 ) : # 이동전에 그곳이 탈출 구 인지 확인함
            print(next[3]) # 여기서 탈출
            # print(board)
            exit()
          else :
            dq.append(next)
            board[next[0]][next[1]] = "J"

print("IMPOSSIBLE")

# print(board)
# print(visit)
# print("j_pos : ",j_pos)
# print("f_pos : ",f_pos)

 

# 해결방법

## 문자열은 변경 할 수 없다.

• 지훈이의 이동(방문)을 표기하기 위해서 만들었던 board에서 그 값을 바로 수정하려 했지만, 문자열은 수정이 불가능한 object이다 그렇기 때문에 문자열이 아닌, 2중 리스트로 표현했다. 
• 이건 원래 알고 있지만 매번 헷갈린다.. 이제는 고민말고 무조건 2차원 배열로 받는게 좋을거 같다.

# 변경 전

[['####'], 
 ['#FF#'], 
 ['#FF#'], 
 ['#.F#']]

# 변경 후

[['#', '#', '#', '#'], 
 ['#', 'F', 'F', '#'], 
 ['#', 'F', 'F', '#'], 
 ['#', '.', 'F', '#']]
 
 
 # 이렇게 받아오면 된다.
 line = list(sys.stdin.readline().strip())

 

## 불의 발화 지점은 한곳이 아닌 여러 곳일 수 있다.

• 해당 케이스를 생각하지 못하고 있었다. 이 부분만 변경하니까 정답이 될 수 있었다. 당연히 불의 발화 지점은 한 곳일거라 생각했고, 딱 한곳만 입력받고 flag를 세워서 더이상 불의 발화지점을 검사하지 않도록 했었다. 그러나 불의 발화지점을 여러곳이 가능했다. 

f_starting = list() # 발화 지점인 곳들을 저장하기 위한 리스트

# ... 코드 생략 ...

for i in range(R) :
  line = list(sys.stdin.readline().strip())
  board.append(line)
  if j_flag :
    for j in range(C) :
      if line[j] == "J" :
        j_pos[0] = i; j_pos[1] = j;
        j_flag = False

  for j in range(C) :
    if line[j] == "F" :
      f_starting.append( (i,j) ) #발화 지점을 추가해준다.

# ... 코드 생략 ...

# 이후 큐에 발화지점을 넣어준다
dq = deque()
for f in f_starting :
  dq.append((f[0],f[1],"F",1))

 

## 굳이 visit 리스트를 만들고 관리할 필요는 없는거 같다.

• 때에 따라 다르지만, 여러개가 동시의 BFS를 통한 탐색이 진행된다면, 굳이 그런 상황이 아니더라도, visit 리스트를 만들지 않고, board에 상황을 표시하는 것도 괜찮은거 같다.
• 먼저 메모리를 아낄 수 있을거라는 생각이 들었다.
• 지훈이의 이동경로와 불의 이동경로를 board위에 "F" , "J"로 바꿔주면서 visit를 표기했다.

 

## 핵심 전략

• 지훈이는 불에 잡히면 안된다. 
• 지훈이는 불에 잡히기 전에 끝지점에 도착한다면 탈출이 가능하다.

이 두 조건을 만족시키기 위해서 고민했다. 불이 먼저 가야하나 지훈이가 가야하나에 대한 생각이었다. 근데 불이 지훈이를 잡는다는 생각이 아니라, 지훈이가 불이 번진 곳을 피해가면 모든 조건을 검사할 필요가 없다는 생각이 들었다.

큐에 불을 먼저 넣고 지훈이를 넣었다. 그리고 불이 번지고 지훈이가 한칸 이동 하는 것 한 단계라고 생각했다.

1. 큐에서 불을 빼고 불이 4방향으로 번진다.
2. 불이 다 빠졌다면 지훈이가 빠질 것이다. 지훈이는 불이 방문한 경로를 피해서 방문한다.
3. 지훈이의 다음 경로가 탈출지점이라면 몇단계인지를 print하고 종료시킨다.
4. 아니라면 계속 반복하다가, 결국 큐가 빌때까지 지훈이가 탈출하지 못한다면 미로를 탈출 할 수 없는 경우이다.

 

여기서 불의 이동 조건에는 "." 과 "J" 지훈이가 있었던 곳들이 방문 가능하다. 왜냐하면 지훈이는 불이 번지는 것을 보고난 후 이동이 가능한 약간 "신"과 같은 존재이기 때문이다. 결국 불이 방문했던 J는 지훈이가 있었던 곳이지 지훈이의 현재 위치는 아니기 때문이다.