백준/ Gold 4 문제 , 백준 파이썬 3055 , 탈출 [BFS]

백준/ Gold 4 문제 , 백준 파이썬 3055 , 탈출 [BFS]

 

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
개인적으로 웃겼던 문제였다. S 가 고슴도치인데 D가 고슴도치라고 잘못생각해서 아니 이게 왜안되지? 를 연발하다가 뒤늦게 알아차리고 허무하게 풀렸던 문제

 

문제 출처

 

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

3055번: 탈출

 

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우 움직임.

 

2. R,C 입력 받기

 

3. R행의 MAP 리스트 입력받기

 

 

 

2. BFS

 

우선 bfs 함수에 물 위치랑 고슴도치 위치를 각각 전달 받는다.

 

물이 퍼질시에는 땅이나 고슴도치 자리를 만나게 되면 모두 물로 바꿔주었고,

 

고슴도치가 이동할때는 땅으로 이동할때만 바꿔주었다.

 

이때 boo 변수는 한번이라도 이동이 있으면 True로 변경 되는데 만약 이동이 없을 시에는 False로 남게 된다.

 

이때는 고슴도치가 더 이상 비버의 굴로 이동할 수 없는 상태이므로 KAKTUS를 리턴시킨다.

 

이때 내가 한 실수는 KAKTUS를 bfs 함수내에서 출력시키고 프로그램을 종료시켰다.

 

하지만, 이렇게 하게되면 물이 이동할 수 없는 경우를 고슴도치가 이동할 수 없다고 잘못 해석하여 고슴도치가 더 이동할 수 있음에도 프로그램을 종료시켜버리는 경우가 생겼다.

 

그러므로 KAKTUS를 리턴하고 처리하는 식으로 바꿨다.

 

 

만약 고슴도치가 이동하다가 비버의 굴을 만나게 되면 바로 True를 리턴 시켜버린다.

 

이외에는 None 리턴이다.

 

 

 

3. BFS 호출 및 return 값 처리

물과 고슴도치 각각 dq를 선언한다.

 

이후 while 문 내에서 이중 for 문을 돌려 해당 MAP의 고슴도치와 물의 위치를 dq에 각각 넣어준뒤 한꺼번에 bfs()에 넣어 호출 시킨다.

 

이때 주의할점은 물이 이동할자리로는 고슴도치가 이동할 수 없으므로 물의 dq1 을 먼저 넣어 bfs()를 호출 시킨뒤에 고슴도치 dq2 를 넣어 실행한다.

 

물의 bfs() 리턴값을 필요없으므로 호출만하고 고슴도치 bfs() 의 리턴 값만 처리해준다.

 

매번 while 문이 한번 돌때마다 고슴도치가 한번 이동하는 것이므로 cnt 변수를 통해 시간을 카운트 해준다.

 

만약 True 를 리턴받았다면 비버의 굴에 도착한 것이므로 cnt 를 출력시킨뒤에 종료하고,

 

만약 KAKTUS 를 리턴 받았다면, 더 이상 고슴도치는 이동할 수없으므로 KAKTUS를 출력하고 while 문을 종료시킨다.

 

 

 

 

 

정답

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

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]

R,C=map(int,input().split())
MAP=[list(input().rstrip()) for _ in range(R)]

def bfs(x):
    boo=False
    if x==dq1:
        while dq1:
            X,Y=dq1.popleft()
            for i in range(4):
                mx,my=X+vertical[i],Y+parallel[i]
                if 0<=mx<R and 0<=my<C:
                    if MAP[mx][my]=='.' or MAP[mx][my]=='S':
                        boo=True
                        MAP[mx][my]='*'
    elif x==dq2:
        while dq2:
            X,Y=dq2.popleft()
            for i in range(4):
                mx,my=X+vertical[i],Y+parallel[i]
                if 0<=mx<R and 0<=my<C:
                    if MAP[mx][my]=='.':
                        MAP[mx][my]='S'
                        boo=True
                    if MAP[mx][my]=='D':
                        return True
    if boo==False:
        return 'KAKTUS'
    
    return None
    
dq1=deque()  # 물
dq2=deque()  # 고슴도치

visited=[[False for _ in range(R)] for _ in range(C)]
cnt=0
while True:
    for i in range(R):
        for j in range(C):
            if MAP[i][j]=='*':
                dq1.append([i,j])
            if MAP[i][j]=='S':
                dq2.append([i,j])
    bfs(dq1)
    result=bfs(dq2)
    cnt+=1
    if result==True:
        print(cnt)
        break
    if result=='KAKTUS':
        print('KAKTUS')
        break