[백준 / Python] 3055번 탈출 | 초코더

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

3055번: 탈출

 

문제

.(빈곳) *(물) X(돌) D(비버굴) S(고슴도치) 가 주어지고 

고슴도치가 비버굴로 이동하기까지 걸리는 최소시간을 구하는것.

단, 물에 잠기면 이동할 수 없고, 돌이 있는 곳으로도 이동할 수 없다.

 

풀이

1. 물, 고슴도치가 있는 위치를 queue에 담는다.

   - 여기서 주의해야할점은 물은 append(), 고슴도치는 appendleft()를 해주어야합니다!

     예시로 2 2 가 들어오면 답은 '1'이 나와야하는데 물이 먼저 queue에 담겨서 고슴도치가 아예이동 못하는

               * *

               DS

      걸로 간주해버려서 답은 'KAKTUS'가 출력됩니다. 그래서 고슴도치를 queue의 왼쪽에 담아주어서 먼저 탐색합니다.

      (이 오류 찾느라 애 많이 먹었어요 ㅜㅜ)

2. 굴이 있는 위치는 target변수에 저장해준다.

3. 물, 고슴도치 있는곳을 BFS 탐색하며 고슴도치가 움직일때마다 +1해준다.

4. 고슴도치 탐색도중 굴을 만나면 탐색종료

    - 여기서 주의해야 할점은 while문을 벗어나서 또다른 탐색을 하면 안되므로 flag변수를 주고 flag가 변하면

       while문을 중단시켜주어야합니다.

      예시로 2 2 가 들어올경우 while문이 종료되지 않고 계속탐색되면 답은 2가 나와야하는데 2+2=4가 나온다 

                S .

                . D

 

느낀점

우선 이문제는 전체코드를 짜는것보단 중간중간 오류들을 잡아주고 반례를 생각하느라 오래걸렸어용 ㅜㅜ

그런데 그 반례를 생각해내는것도 정말 중요한듯 하네요..

 

전체코드

import sys
from _collections import deque
r,c=map(int,input().split())
maps=[list(p for p in sys.stdin.readline().strip()) for _ in range(r)]
visit=[[0]*c for _ in range(r)]
dr=[1,0,-1,0]
dc=[0,-1,0,1]
queue=deque()

#물,고슴도치 위치 queue에 담기
#굴의 위치는 target에 저장
for i in range(r):
    for j in range(c):
        if maps[i][j]=='*':
            queue.append([i,j])
        elif maps[i][j]=='S':
            queue.appendleft([i,j])
        elif maps[i][j]=='D':
            target_r=i
            target_c=j

flag=False
#물과 고슴도치 위치에서 BFS탐색
while queue:
    # 굴에 도착하고 나면 while문 탈출
    if flag:
        break
    pr, pc = queue.popleft()
    for i in range(4):
        nr,nc=pr+dr[i],pc+dc[i]
        if nr<0 or nr>=r or nc<0 or nc>=c:
            continue

        #물
        if maps[pr][pc]=='*':
            if maps[nr][nc]=='.' or maps[nr][nc]=='S':
                maps[nr][nc]='*'
                queue.append([nr,nc])

        #고슴도치
        elif maps[pr][pc] == 'S':
            if maps[nr][nc] == '.':
                maps[nr][nc] = 'S'
                visit[nr][nc] = visit[pr][pc] + 1
                queue.append([nr,nc])
            #굴에 도착하면 탈출
            elif maps[nr][nc] == 'D':
                flag=True
                visit[nr][nc]=visit[pr][pc]+1
                break

#굴에 도착하지 못하면 visit[굴]이 0이므로
if visit[target_r][target_c]==0:
    print('KAKTUS')
else: print(visit[target_r][target_c])