[백준 16137번] 견우와 직녀(파이썬)

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

16137번: 견우와 직녀

문제의 설명이 상당히 불친절한 문제입니다.

구글링의 코드를 참고하고서야

문제설명을 제대로 이해했습니다.

 

이 문제에서 포인트 몇가지 집어드리겠습니다.

 

1. 빈칸에 오작교를 설치할 수 있는 경우

-->0이 교차하는 지점을 제외합니다.

주변에 이미 놓여있는 오작교가 있는 거랑 무관합니다.

(저는 주변에 오작교가 있으면 넣지 못하는 줄 알고 풀었으나

예시코드를 보니 아니었습니다.)

 

2. 오작교를 연속으로 건너지 않는다

-->이런 설명이 있어서

'오작교 설치를 연속으로만 하지 않으면 되는 거 아닌가'

라는 생각이 있을 수 있습니다.

하지만 오작교를 추가로 설치해서 건너는 건 딱 한번뿐.

기존오작교->추가오작교

순으로 가는게 안된다는 의미이지

추가오작교를 쉬었다가 또 건넌다는 의미는 아닙니다.

 

3. 주기가 되면 건넌다

-->주기가 될 때까지 멈췄다가 건너는 케이스도 존재하니

이 부분도 반영해야합니다.

# 백준 16137번 견우와 직녀
from collections import deque

N, M = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]
put = []
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

#오작교를 넣을 수 있는 자리를 체크하기
for x in range(N):
    for y in range(N):
        if room[x][y] == 0:
            flag = True
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue

                if room[nx][ny] == 0:
                    nd = (d + 1) % 4
                    n2x = x + dx[nd]
                    n2y = y + dy[nd]

                    if 0<=n2x<N and 0<=n2y<N:

                        if room[n2x][n2y] ==0 or room[n2x][n2y]>1:
                            flag = False
                            break
                    nd = (d - 1) % 4
                    n2x = x + dx[nd]
                    n2y = y + dy[nd]

                    if 0<=n2x<N and 0<=n2y<N:

                        if room[n2x][n2y] ==0 or room[n2x][n2y]>1:
                            flag = False
                            break

            if flag == True:
                put.append([x, y])

q = deque()
q.append([0, 0, 0, 0,False])
answer = 1e9
INF=1e9
visited=[[[1e9]*N for _ in range(N)] for _ in range(2)]

while q:
    x, y, cnt, flag,cross = q.popleft()
    if cnt > answer:
        continue
    if x == N - 1 and y == N - 1:
        answer = min(answer, cnt)
        continue

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        #범위 체크
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        #지나갈 수 있는 곳
        if room[nx][ny] == 1 and visited[flag][nx][ny]>cnt+1:
            q.append([nx, ny, cnt + 1, flag,False])
            visited[flag][nx][ny]=cnt+1
        #지나갈 수 없는 곳
        elif room[nx][ny] == 0 and [nx, ny] in put and flag==False and cross==False:
            if (cnt + 1) % M == 0:
                t=cnt+1
            else:
                #주기가 될떄까지 기다렸다 건너는 경우
                t=cnt+(M-cnt%M)
            if visited[1][nx][ny]>t:
                q.append([nx, ny, t, 1,True])
                visited[1][nx][ny]=t
        #이미 놓아진 다리
        elif room[nx][ny] > 1 and cross == False:
            if (cnt+1)%room[nx][ny]==0:
                t=cnt+1
            else:
                #주기가 될떄까지 기다렸다가 건너는 경우
                t=cnt+(room[nx][ny]-cnt%room[nx][ny])
            if visited[flag][nx][ny]>t:
                q.append([nx,ny,t,flag,True])
                visited[flag][nx][ny]=t

print(answer)

 

3차원 배열을 쓰면서 BFS에 활용하는 방법을 익히는 데는 좋지만...

문제 설명이 상당히 불친절해서

고생을 많이 하게 만들었습니다.