[백준-1400] 화물차 (Python)

문제링크 - https://www.acmicpc.net/problem/1400

1400번: 화물차

---

[풀이]

 

- 입력 받을 때 출발지 창고와 배송지 창고를 따로 저장해두었고, 교차로 정보는 Dictionary로 저장해두었다.

 

- '-' 이면 동서 방향의 신호등이 먼저 켜지고, 남북 방향의 신호등이 나중에 켜지므로 동서 방향의 신호등 시간은 그대로 두고 남북 방향의 신호등 최대 시간은 둘의 신호등 합으로 바꾸고, sum이라는 키를 새로 만들어서 해당 교차로 신호등의 전체 주기를 따로 저장해두었다.

 

- '|' 일 때는 동서 방향의 신호등 시간을 둘의 합으로 바꾸었다. sum 값을 따로 저장해준 이유는 시간 단위로 교차로 정보를 확인하면서 각각의 교차로 주기가 다 되면 둘의 합을 더해주고 방향을 바꿔주었다. 이 부분은 설명하기가 까다로웠다...

 

- 일반적인 bfs와 동일한데 다음 칸이 교차로이면 해당 교차로의 신호등 방향이 이동하려는 방향과 일치한지 체크하고 일치하면 뻗어나가고, 그렇지 않으면 제자리인 상태로 큐에 넣어주었다.

---

from collections import deque
def bfs():
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    q = deque()
    q.append((sx, sy))
    visit[sx][sy] = True
    t=0
    while q:
        size=len(q)
        t+=1
        while size:
            x, y = q.popleft()
            for dir in range(4):
                nx,ny=x+dx[dir], y+dy[dir]
                if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
                    if maps[nx][ny]=='.': continue
                    elif maps[nx][ny]=='#':
                        visit[nx][ny]=True
                        q.append((nx,ny))
                    elif "0"<=maps[nx][ny]<="9":
                        num=int(maps[nx][ny])
                        if 0<=dir<=1:
                            if intersections[num]['dir'] == '|':
                                visit[nx][ny]=True
                                q.append((nx,ny))
                            else:
                                q.append((x,y))
                        else:
                            if intersections[num]['dir'] == '-':
                                visit[nx][ny]=True
                                q.append((nx,ny))
                            else:
                                q.append((x,y))
                    else:
                        # 도착
                        return t
            size-=1

        for i in range(10):
            if intersections[i]==False: continue
            if intersections[i]['dir']=='-':
                if t>=intersections[i]['a']:
                    intersections[i]['a']+=intersections[i]['sum']
                    intersections[i]['dir']='|'
            else:
                if t>=intersections[i]['b']:
                    intersections[i]['b']+=intersections[i]['sum']
                    intersections[i]['dir']='-'

    return "impossible"

while True:
    n,m=map(int, input().split())
    if n==0 and m==0: break
    maps=[]
    intersection_cnt=0
    sx,sy,ex,ey=-1,-1,-1,-1
    for i in range(n):
        tmp=list(input())
        for j in range(m):
            if tmp[j]=='A':
                sx,sy=i,j
            elif tmp[j]=='B':
                ex,ey=i,j
            elif "0"<=tmp[j]<="9":
                intersection_cnt+=1
        maps.append(tmp)
    intersections=[False for _ in range(10)]
    for _ in range(intersection_cnt):
        tmp=input().split()
        intersections[int(tmp[0])]={'dir': tmp[1], 'a': int(tmp[2]), 'b': int(tmp[3])+int(tmp[2]),'sum':int(tmp[3])+int(tmp[2])} if tmp[1]=='-' else {'dir': tmp[1], 'a': int(tmp[2])+int(tmp[3]), 'b': int(tmp[3]),'sum':int(tmp[3])+int(tmp[2])}
    visit=[[False for _ in range(m)] for _ in range(n)]
    print(bfs())
    enter=input()