백준 16137번: 견우와 직녀

백준 16137번: 견우와 직녀

import heapq
import sys
input = sys.stdin.readline
N,M=map(int,input().split()) #N:땅 크기, M:오작교 주기
graph = [list(map(int,input().split())) for _ in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

#한 번 지은 오작교는 한 번만 유지할 수 있다.
#이미 오작교를 짓기로 예정한 곳, 절벽이 가로와 세로로 교차하는 곳에는 오작교를 놓을 수 없다.
#(0,0) -> (N-1,N-1)

def isPossibleCoord(x,y):
    row_count = 0
    col_count = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if(0<=nx<N and 0<=ny<N and graph[nx][ny]==0):
            if i%2==0:
                row_count += 1
            else:
                col_count += 1
    if row_count>0 and col_count>0:
        return True
    else:
        return False
def bfs():
    queue = []
    heapq.heappush(queue, (0,0,0, False))
    visit = [[0 for _ in range(N)] for _ in range(N)]
    visit[0][0] = 1
    while queue:
        t,x,y,step = heapq.heappop(queue)
        #step = x,y가 오작교인지 확인하는 flag변수 (step==True면 이번에는 오작교 건널 수 x)
        #isSet = 새로운 오작교를 하나 만든 상태인지 확인하는 flag변수
        visit[x][y]=1
        if(x==N-1 and y==N-1):
            return t
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<N and (visit[nx][ny]==0):
                if graph[nx][ny]==1:
                    heapq.heappush(queue,(t+1, nx, ny, False))
                if step==True and graph[nx][ny]!=1: #0,-1,2,... 모든 오작교 후보들.
                    continue
                elif graph[nx][ny]>1: #이미 만들어진 오작교
                        nextTime = (t // graph[nx][ny] + 1) * graph[nx][ny]
                        heapq.heappush(queue,(nextTime, nx,ny, True))
    return -1

result = 1e9
for i in range(N):
    for j in range(N):
        if graph[i][j]==0:
            if(isPossibleCoord(i,j)==False): #가로 세로가 교차해서 오작교를 만들 수 없는 절벽이 아님.
                graph[i][j]=M
                tmp_result = bfs()
                if(tmp_result!=-1):
                    result = min(result,tmp_result)
                graph[i][j]=0

print(result)

이 문제도 구현 자체는 어렵지 않았는데... 엣지케이스때문에 좀 골치가 아팠다.

8 2 

1 1 1 1 0 1 1 1 

1 1 0 1 0 1 0 1 

0 0 0 1 1 1 0 1 

0 0 0 0 0 0 0 1 

0 0 0 0 0 1 0 1 

0 0 0 0 0 1 1 1 

0 0 0 0 0 0 0 10 

0 0 0 0 0 0 1 1

Answer = 20;

질문 게시판에 올라와있는 반례인데, 처음에는 heapq로 단순 bfs 활용해서 풀었더니 저 케이스가 틀리게 나왔다.

import heapq
N,M=map(int,input().split()) #N:땅 크기, M:오작교 주기
graph = [list(map(int,input().split())) for _ in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

#한 번 지은 오작교는 한 번만 유지할 수 있다.
#이미 오작교를 짓기로 예정한 곳, 절벽이 가로와 세로로 교차하는 곳에는 오작교를 놓을 수 없다.
#(0,0) -> (N-1,N-1)

t = 0
x,y = 0,0

queue = []
heapq.heappush(queue, (t,x,y,False,False))
visit = [[0 for _ in range(N)] for _ in range(N)]
def isPossibleCoord(x,y):
    row_count = 0
    col_count = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if(0<=nx<N and 0<=ny<N and graph[nx][ny]==0):
            if i%2==0:
                row_count += 1
            else:
                col_count += 1
    if row_count>0 and col_count>0:
        return True
    else:
        return False

for i in range(N):
    for j in range(N):
        if graph[i][j]==0:
            if(isPossibleCoord(i,j)==True): #가로 세로가 교차해서 오작교를 만들 수 없는 절벽은 -1으로 수정해준다.
                graph[i][j]=-1

while queue:
    t,x,y,step,isSet = heapq.heappop(queue)
    visit[x][y] = 1
    #step = x,y가 오작교인지 확인하는 flag변수 (step==True면 이번에는 오작교 건널 수 x)
    #isSet = 새로운 오작교를 하나 만든 상태인지 확인하는 flag변수
    if x==N-1 and y==N-1:
        print(t)
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<N and 0<=ny<N and visit[nx][ny]==0:
            if graph[nx][ny]==1:
                heapq.heappush(queue,(t+1, nx, ny, False,isSet))
            if step==True and graph[nx][ny]!=1: #0,-1,2,... 모든 오작교 후보들.
                continue
            else:
                if isSet==False and graph[nx][ny]==0: #오작교를 만들 수 있는 절벽, 임의로 생성한다.
                    nextTime = (t//M + 1)*M #ex)M은 11이고 현재 t=1일때, 11이 되기까지 기다려야됨: (1//11 + 1)*11 = 11
                    heapq.heappush(queue,(nextTime, nx,ny, True,True)) #M분 주기
                elif graph[nx][ny]>1: #이미 만들어진 오작교
                    nextTime = (t // graph[nx][ny] + 1) * graph[nx][ny]
                    heapq.heappush(queue,(nextTime, nx,ny, True,isSet))

이게 처음 작성한 풀이이다.
기본 bfs의 경우에는 경로상 장애물이 있거나 하지는 않으니 가장 처음 도착점에 도달한 케이스가 무조건 최단경로가 되는게 맞는데, 이 문제의 경우에는 오작교 견설과 관련해서 조건이 좀 까다로운 편이었다. 그래서 도착점에 도달하기 직전가지는 다른 경로보다 느리다가, 마지막 도착점에 도달할때는 다른 경로보다 빨라지는 경우가 존재한다(!) 따라서 visit를 기존의 bfs처럼 바로 바로 1으로 찍어주면 안 되는 문제인 것이다.
t를 기준으로 빨리 정렬해서 최단경로를 구하게하려고 나름 heapq를 쓴거였는데, visit에 문제가 있을 줄은(..) 그래서 이 문제는 굳이 heapq 쓰지 않아도 되고, 그냥 deque써도 된다.

여튼 뭐가 문제인지를 찾고 나서, 처음에는 visit를 각 경로마다 복사해줘서 풀어야되는가 생각을 했다. 당연히 메모리초과에 시간초과났다(...) 그래서 이런 저런 방법을 고민을 했다... visit에서 t를 기준으로 찍는 방법도 시도했었는데, 마지막에 가서 역전하는 경우이기 때문에 그걸로는 안된다. isSet을 기준으로 heapq를 정렬하게 하는 코드도 짜봤는데, 이건 아니었다. 아무튼 그래서 인터넷에 올라와있는 다른 풀이를 좀 찾아보다가... 나는 경로별로 자율적으로 오작교를 만들 거나/만들지 않거나의 경우의 수로 코드를 작성했었는데, 반대로 만들 수 있는 오작교 각각에 대해서 bfs를 해주는 풀이가 있었다.

아무래도 정석 bfs로 했을 때 경로가 갈리는 이유는 오작교이기 때문에, 이렇게 풀어야 최단시간인 오작교의 위치를 찾을 수 있는 것 같다. (추가로 만들 오작교를 지정해줬을 뿐, 안 지나도 되는 거라 아무것도 지나지 않는 경우의 수도 고려 가능하다.) 나는 heapq를 기준으로 풀고 있었어서, 어차피 최단 t를 기준으로 정렬해주니까 그냥 정석 bfs대로 visit를 체크해줘도 상관 없었다. result도 그냥 제일 처음에 나오는 값이 무조건 최단 경로가 맞다. 하지만 deque를 기준으로 푸는 경우에는 visit를 t를 기준으로 갱신해줘야할 것이다.