배달 파이썬 백준 1175

문제

input

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

output

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

TODO

0. 시작점에서 4방향으로 bfs 시작
1. 해당 위치에 들어온 방향을 체크하고, 다음 나아갈 방향은 들어온 방향으로 못나가게한다. 
2. C를 한 번 찾지 않은 이상 해당 위치에 들어온 방향으로 다시 들어올 수 없다 
	-> 헛짓거리임
3. C를 처음 찾으면 현재 큐에 있는것들까지 전부 확인
3-1. 같은 시간내에 C로 들어올 수 있는 방향들을 체크한다.
3-2. 처음 찾은 C를 '.'으로 바꾼다.
4. C로 들어온 방향들로 다시 시작한다. 
5. 찾은 C의 갯수가 2이면 찾은 시점을 return

CODE

import sys 
from collections import deque 

def find_path(start):
    q = deque(start)
    visit = [[[1 for _ in range(m)] for _ in range(n)] for _ in range(4)]
    find_c = 0 
    find_save_point = deque()
    while q : 
        x,y,d,cnt = q.popleft()
        for before,(px,py) in enumerate(zip(dx,dy)): 
            if before == d : 
                continue 
            nx,ny= x+px,y+py
            if 0<=nx<n and 0<=ny<m and maps[nx][ny] != '#' and visit[before][nx][ny] : 
                if maps[nx][ny] == 'C' :
                    if not find_save_point :
                        find_c +=1 
                        if find_c == 2 : # 두개 다 찾음
                            return cnt+1
                    elif find_save_point[0][0] != nx or find_save_point[0][1] != ny : #처음 찾은 C와 다른 C임 
                        continue  
                    find_save_point.append((nx,ny,before,cnt+1))
                else : 
                    if find_save_point:
                        continue 
                    visit[before][nx][ny] -=1 
                    q.append((nx,ny,before,cnt+1))
        if not q and find_save_point: 
            visit = [[[1 for _ in range(m)] for _ in range(n)] for _ in range(4)]
            maps[find_save_point[0][0]][find_save_point[0][1]] = '.'
            while find_save_point: 
                q.append(find_save_point.pop())
    return -1 

n,m = map(int,sys.stdin.readline().split())
dx = [0,1,0,-1]
dy = [1,0,-1,0]
maps = [] 
start = [] 
for i in range(n): 
    line = list(sys.stdin.readline()[:-1])
    if not start and 'S' in line: 
        start.append((i,line.index('S'),-1,0))
    maps.append(line)
print(find_path(start))

회고

한 위치에 방문하는 회수가 4라면 모든 방향에서 들어온걸 체크할줄 알았다.
그래서

visit = [[4 for _ in range(m)] for _ in range(n)]

으로 저장하고 방문처리했었는데.. 예시나 질문에 올라온 반례는 전부 맞지만.. 계속 1%에서 틀렸다.

생각했던건 같은 방향으로 두번 들어오는걸 처리하기 위한것이다. 따라서 방향차원을 하나 더 만들었고 해결할 수 있었다.

visit = [[[1 for _ in range(m)] for _ in range(n] for_ in range(4)]