백준 3055_탈출

탈출(백준 3055)

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

조건문을 어설프게 쓰면 안된다는 것을 다시 한번 뼈져리게 느꼈다…
가장 위의 if 의 조건문에 ‘애초에 걸러내야 할 조건’을 넣어버린 후,
continue를 하였기에
어마어마한 소모가 있었다

(아마 무의식적으로 걸러내는 조건을 continue로 넣으면
이 밑은 내가 예상한 데이터만 오겠지??
싶었나 보다)

단순히 ‘예제’ 입력만 통과한다고 좋아할 게 아니라,
내가 짠 코드를 조금 더 자세히 봐야 한다는 걸 반성할만한 문제였다

Code

import sys
from collections import deque

inp = sys.stdin.readline

row, column = map(int,inp().split())
Graph = [list(inp().strip()) for _ in range(row)]

# 물과 고슴도치를 각각 BFS 따로 돌리기

def bfs():
    objque = deque()
    hegiVisit = [[0] * column for _ in range(row)]

    # 물 먼저 넣어주기
    for i in range(row):
        for j in range(column):
            if Graph[i][j] == '*':
                objque.append(['w',i,j])

    for i in range(row):
        for j in range(column):
            if Graph[i][j] == 'S':
                objque.append(['h',i,j])
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while objque:
        obj,px,py = objque.popleft()

        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]
            if 0 <= nx < row and 0 <= ny < column:
                if obj == 'w': # 물인 경우
                    if Graph[nx][ny] == '.':
                        objque.append(['w',nx,ny])
                        Graph[nx][ny] = '*'
                else: # 고슴도치인 경우
                    #if Graph[nx][ny] == 'X' or Graph[nx][ny] == '*':
                    #    continue

                    if Graph[nx][ny] == 'D':
                        return hegiVisit[px][py] + 1
                    
                    if Graph[nx][ny] == '.' and hegiVisit[nx][ny] == 0:
                        hegiVisit[nx][ny] = hegiVisit[px][py] + 1
                        objque.append(['h',nx,ny])

    return -1

result = bfs()

if result == -1:
    print('KAKTUS')
else:
    print(result)

해결 아이디어

1. 물의 움직임과 고슴도치의 움직임 모두 queue에 넣는다
   다만 처음의 경우에 한해 ‘물’부터 넣어준다
2. queue에 넣을때, ‘물’인지 ‘고슴도치’인지 구분한 후,
   그에 맞게 처리한다
3. 고슴도치가 움직일 수 없다면 -1을, 비버 굴에 도착했다면,
   그 수치를 반환한다.
4. 출력!