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

[백준] 3055번 - 탈출

풀이 시간: 50분 이내

유사 문제: 4179

(풀이1) 물, 고슴도치 deque을 각각 생성한 방식(고슴도치→물 이동)

1) 문제 해결 아이디어

이 문제는 물이 차기 전에 고슴도치가 안전하게 비버의 굴로 이동하기 위한 최소 시간을 구하는 문제로 BFS로 풀이가 가능하다. 혼자서 푸는데는 성공했지만 나중에 복습을 한번 해봐야할 문제!

매 분마다 고슴도치는 현재 있는 칸과 인접한 4칸 중 하나로 이동할 수 있고 물은 인접한 4방향으로 모두 이동한다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 물→고슴도치 순으로 이동시켜야 하지만 고슴도치→물 순으로이동시켜도 전혀 문제가 되지 않는다.

그리고 고슴도치가 안전하게 비버의 굴로 이동할 수 없다면 "KAKTUS"를 출력해야한다.

고슴도치가 비버의 굴로 이동할 수 없는 경우는 비버굴(D)에 도달하지 못했는데 더이상 꺼낼 고슴도치 좌표(queueS)가 없을 때이다.

 

Q. 고슴도치→물 순으로 이동해도 문제가 없는 이유는?

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없기 때문에 물→고슴도치 순으로 이동시키면 자연스레 물이 찬 곳으로는 고슴도치가 이동할 수 없게 된다. 하지만 고슴도치→물 순으로 이동시킨다고 해서 문제가 될 건 없다. 고슴도치가 물이 찰 예정인 칸으로 이동했더라도 물이 이동할 때 좀 전에 고슴도치가 이동했던 곳에 값(*)을 덮어쓰기 때문이다. (결과상으로는 graph에서 고슴도치가 이동하지 못하고 물이 이동한 것으로 보임)

 

[참고] https://wookcode.tistory.com/167

[백준] 3055번, 탈출 (Python)

 

예를 들어 초기 입력이 아래와 같을 때 3분 만에 D에 도달하는데 성공했다.

3 3
D.*
...
.S.

 

초기 입력이 아래와 같을 때 D에 도달하는데 실패했다.

3 3
D.*
...
..S

<고슴도치 이동 조건>

1. 빈 곳(.) 일 때

2. 비버 굴(D) 일 때

 

<물 이동 조건>

1. 빈 곳(.) 일 때

2. 고슴도치가 지나갔던 곳(숫자)일 때

 

첫번째 오류. 런타임 에러(TypeError)

12~13줄 코드를 넣어주지 않아서 생겼던 오류이다.

이 오류가 생긴 이유는 10줄에서 popleft()한 좌표의 값이 문자(*)면 22줄에서 int와 str을 더하려고 할 때 오류가 나기 때문이다. 고슴도치→물 순으로 이동하기 때문에 생길 수 있는 문제다. 고슴도치가 이동하면서 빈곳을 큐에 넣을 당시에는 칸의 좌표값이 숫자였을테지만 물이 이동하면서 *으로 덮어쓸 때 큐에서 그 값을 빼주는 등의 처리를 따로 하지 않기 때문에 나중에 값을 꺼낼 때 그 좌표의 값이 물(*)인지 숫자인지를 꼭 확인해야한다!!

 

[참고] https://velog.io/@johnny/baek-3055

백준 3055번: 탈출 (python)

[참고] https://kyun2da.github.io/2020/09/22/escape/

[백준/Python] 3055 탈출 - Kyun2da Blog

 

2) 소스코드

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

# BFS
def bfs():
  while True:
    # 1. 고슴도치 이동
    for i in range(len(queueS)):
      x, y = queueS.popleft()
      # 혹시 물로 변한 것이면 다음 위치 검사
      if(graph[x][y] == '*'):
        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] == '.'):
            queueS.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1
          # 비버굴(목표점)이면 바로 값 리턴
          elif(graph[nx][ny] == 'D'):
            return graph[x][y] + 1
    # 2. 물 이동
    for i in range(len(queueW)):
      x, y = queueW.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]) is int):
            queueW.append((nx, ny))
            graph[nx][ny] = '*'
    '''
    # 1분 지난 후 고슴도치, 물 이동 결과
    for i in graph:
      print(i)
    print()
    '''
    # 꺼낼 고슴도치가 없으면
    if not queueS:  return "KAKTUS"

r, c = map(int, input().split())
# r*c (.: 빈 곳, *: 물, X: 돌, D: 비버 굴, S: 고슴도치)
graph = [list(input().strip()) for _ in range(r)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dLoc = [0, 0]     # 비버 굴
queueW = deque()  # 물
queueS = deque()  # 고슴도치
#visited = [[0] * c for _ in range(r)]

# 고슴도치(S)와 물(*) 위치 찾기
for i in range(r):
  for j in range(c):
    # 비버 굴이면 
    if(graph[i][j] == "D"):
      dLoc = [i, j]
    # 고슴도치면 삽입, 방문 처리
    elif(graph[i][j] == 'S'):
      queueS.append((i, j))
      graph[i][j] = 0
    # 물이면 삽입
    elif(graph[i][j] == "*"):
      queueW.append((i, j))
      #visited[i][j] = 1
  
print(bfs())

<데이터 Type 확인>

type(매개변수)

인자로 전달된 객체의 타입을 리턴

 

[참고] https://codechacha.com/ko/python-type-check/

Python - 데이터 Type 확인 - type(), isinstance()