[파이썬] 백준 1175 : 배달 (골드1)

[파이썬] 백준 1175 : 배달 (골드1)

• 백준 1175 : 배달 (골드1)

---

풀이

방향성 생각

• 비트마스킹 + 상태관리 BFS
• 배달 완료한거는 비트마스킹으로, 이전 방향까지 고려해서 4차원 BFS 사용하기.
• 혹은, C1 -> C2 / C2 -> C1 중 최소값을 고려해도 풀릴 듯 한데, 예외처리가 필요해보인다. (S.C.C 같은 경우)

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()

inside = lambda x,y : 0<=x<W and 0<=y<H
dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W = map(int,input().split())
arr = [list(input()) for _ in range(H)]

V = [[[[-1]*W for _ in range(H)] for _ in range(4)] for _ in range(4)]


# 시작점 찾기, 배달지점 번호매기기 (미리 shift 해놓기)

Q = deque()
targets = {}
cnt = 0
for i in range(H):
    for j in range(W):
        if arr[i][j] == 'S':
            for dire in range(4):   
                Q.append((j,i,dire,0,0))
                V[dire][0][i][j] = 0
        elif arr[i][j] == 'C':
            targets[(j,i)] = 1<<cnt
            cnt += 1

# BFS
find = False
while Q:

    x,y,dire,state,t = Q.popleft()

    # 전부 찾으면 break
    if state == (1<<cnt)-1:
        find = True
        break

    for ndire,(dx,dy) in enumerate(dires):
        nx,ny = x+dx,y+dy
        if inside(nx,ny) and arr[ny][nx] != '#' and V[ndire][state][ny][nx] == -1:

            # 상태 업데이트
            nstate = state
            if arr[ny][nx] == 'C':
                nstate = (state | targets[(nx,ny)])

            # 방향이 다른 경우에만 큐에 추가
            if ndire != dire:
                Q.append((nx,ny,ndire,nstate,t+1))
                V[ndire][nstate][ny][nx] = t+1

print(t if find else -1)

코멘트

. 쉬운문제