[BOJ] 3055 탈출 - python

https://www.acmicpc.net/problem/3055

3055번: 탈출

<- CODE ->

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

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

board = []
visited = [[False for _ in range(C)] for _ in range(R)]
#물, 고슴도치를 큐에 넣고 움직이면서 굴에 들어갔는지 확인할거야
#visited 즉 고슴도치가 움직인 곳은 볼 필요 없겠지?

for _ in range(R):
    board.append(list(input()))

cnt = 0
success = False #굴을 발견했는지
q = deque([])
direction = [(-1,0),(1,0),(0,1),(0,-1)]

#큐에 물, 고슴도치 순으로 넣는다.
for r in range(R):
    for c in range(C):
        if board[r][c] == "*": #물이면
            q.append(("*",0,r,c))

for r in range(R):
    for c in range(C):
        if board[r][c] == "S": #고슴도치면
            q.append(("S",0,r,c))
            visited[r][c] = True

while q: # 큐가 빌 때까지 진행
    what,cnt,now_r,now_c = q.popleft()
    for _r, _c in direction:
        nxt_r, nxt_c = now_r + _r, now_c + _c
        if not (0 <= nxt_r < R) or not (0 <= nxt_c <C): #벽이면
            continue
        if what == "*": #물
            if board[nxt_r][nxt_c] == ".":
                board[nxt_r][nxt_c] = "*"
                visited[nxt_r][nxt_c] = True
                q.append((what,cnt+1,nxt_r,nxt_c))
        else: #고슴도치
            if visited[nxt_r][nxt_c]: #이미 방문했으면
                continue
            if board[nxt_r][nxt_c] == ".": #이동가능
                q.append((what,cnt+1,nxt_r,nxt_c))
                visited[nxt_r][nxt_c] = True
            elif board[nxt_r][nxt_c] == "D": #굴 도착
                success = True
                break
    if success:
        break
if success:
    print(cnt+1)
else:
    print("KAKTUS")

* 풀이방법

• visited를 검사하여 queue에 넣는 bfs를 이용하는 문제라는 것을 알아야 한다.
• 물을 먼저 이동시키고 고슴도치를 이동시킨다.

얻어가는 것

• bfs : 너비 우선 탐색
  • → 매 단계에서 가능한 모든 경우를 탐색한다.
• dfs : 깊이 우선 탐색
  • → 가능한 깊게까지 다 들어간다.

Python｜탐색 알고리즘 뿌시기 (1) DFS, BFS 의 개념과 구현

• input 받기

def input():
    return sys.stdin.readline().rstrip() # 라인으로 받은 뒤 split할 수 있다.

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

for _ in range(R):
    board.append(list(input()))

• 큐에 저장하기
  • 튜플의 형태로 큐에 삽입하여 사용할 수 있다.

q.append(("*",0,r,c))

• 벽 검사하기

for _r, _c in direction:
        nxt_r, nxt_c = now_r + _r, now_c + _c
        if not (0 <= nxt_r < R) or not (0 <= nxt_c <C): #벽이면
            continue

느낀점

"210908"

소요 시간 : 3D 이상

• 2시간 이상 풀어서 안 풀리면 풀이 보자.
• 존재하지 않는 조건에 대해 생각할 필요 없다. 고슴도치가 물에 닿으면 죽는다는 조건은 없었는데 왜 그렇게 생각했지?