17836 - 공주님을 구해라!

확실히 실버와 골드 사이에는 넘을 수 없는 차원의 벽이 있는 것 같습니다. 문제를 한번 더 꼬아놨다고 해야 하나...

(0,0)에 용사가 있고 (N,M) 그러니까 끝자락에 공주가 있습니다. 용사가 공주한테 갈 수 있는 최단거리를 구해서 시간안에 구했으면 최단거리를 출력, 시간 안에 구하지 못했다면 Fail을 출력하면 됩니다.

단, 이 마왕성 안에는 전설의 성검 그람이 존재합니다. 그람을 획득할 경우 모든 벽을 뚫고 가는 개치트 벽뚫기가 가능합니다.

일단 제가 문제를 처음 보고 생각해낸건

1. 검을 획득하는 경우
2. 검을 획득하지 못하는 경우

를 각각 나누어 계산하고 마지막에 후처리로 가장 짧은 시간 내에 공주를 구할 수 있는 값을 도출하는게 제일 베스트인 것 같습니다.

---

기초세팅

먼저 기본적인 선언같은걸 받아옵시다.

from collections import deque
import copy

N,M,T = map(int,input().split())
que = deque()
graph = []
for _ in range(N):
    graph.append(list(map(int,input().split())))
graph2 = copy.deepcopy(graph)

그래프랑 마왕성 크기, 공주 구하는 시간 등을 받아주고 검을 획득하는 경우와 검을 획득하지 못한 케이스를 둘 다 계산해주기 위해서 깊은 복사 deepcopy를 하여 graph와 똑같은 graph2를 하나 만들어주겠습니다.

또한 언제나 BFS 알고리즘을 사용하기 위한 que를 불러와주고

yes_gram = abs(bfs_yesgram(0,0))
no_gram = abs(bfs_nogram(0,0))

전설의 성검 그람을 획득한 경우를 yes_gram, 그람을 획득하지 못한 경우를 no_gram으로 각각 나누어 변수로써 담아주겠습니다.

---

검을 획득하지 못한 경우

자 먼저 더 간단히 계산가능한 검을 획득하지 못한 경우를 살펴봅시다.

테스트케이스를 살펴보면 벽은 1, 전설의 성검 그람은 2로 표기가 되어 있습니다.
만약 BFS를 실행하기 위해서 각 자리 방문수를 단순히 +1씩 증진시킨다면 계산하는 도중 저 벽과 그람의 충돌 가능성이 있습니다.
따라서 저는 음수로 각 자리에 최단거리를 표기해주겠습니다.

dx = [0,0,-1,1]
dy = [1,-1,0,0]

def bfs_nogram(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 

상하좌우 탐색 기준 dx와 dy를 선언해주고 x랑 y, 그러니까 시작점 0,0 부터 받아 4방향 탐색을 쭉 진행해줍시다.

            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] - 1
                que.append([nx,ny])
    return graph[N-1][M-1]

0은 벽도 아니고 성검 그람도 아닌 다음 탐색이 가능한 인덱스이므로 만날 경우엔 전 인덱스 -1로 표기해줍시다.

그리고 탐색이 다 끝난다면 리스트는 0부터 시작하므로 graph[N-1][M-1]을 리턴해주면 검을 획득하지 않고 공주를 구할 수 있는 최단거리가 나오게 됩니다.

위 테스트케이스대로 실행시켜봤을 때 나오는 출력값. 이전 게시글에도 있지만 0,0은 1,0 또는 0,1의 탐색에 재 영향을 받기 때문에 유효한 출력값이 아닙니다. 하지만 문제의 목표는 graph[N-1][M-1]의 공주를 구하는 최단거리이므로 크게 유의미한 값은 아닙니다.

---

검을 획득한 경우

검을 획득한 경우는 두번 나뉘어서 생각해봐야 합니다.

1. 검까지 가는 최단거리
2. 해당 검에서 종료지점 graph[N-1][M-1]까지 가는 최단거리

그러니까 따지고보면 시작점->검 구하고 검->종료지점 구해서 둘이 더하면 된다는 소리입니다.
굳이 안더하고 검에 최단거리 기록해놓고 다시 BFS 돌려두 되구요.

def bfs_yesgram(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 
            if graph2[nx][ny] == 0:
                graph2[nx][ny] = graph2[x][y] - 1
                que.append([nx,ny])`

먼저 초반부는 앞의 BFS 코드와 일치합니다. 일단 검까지 가는 거리를 구해야 하니까요.

            if graph2[nx][ny] == 2:
                graph2[nx][ny] = graph2[x][y] - 1
                for n in range(N):
                    for m in range(M):
                        if n != nx or m != ny:
                            graph2[n][m] = 0
                que.clear()
                que.append([nx,ny])
                break

분기점은 여기서 생깁니다. 만약 전설의 성검(2) 그람을 만났다면 일단 검이 있는 해당 인덱스에 거기까지 가는 최단거리를 기록해줍니다.

상단 테스트케이스대로라면 이런 출력이겠지요?
저 -6자리가 성검 그람을 얻는 최단 거리인 겁니다.
이렇게 그람을 얻었다면 저희는 희대의 개사기 치트 벽뚫기를 시전할 수 있습니다.
이전에 최단거리 기록해둔 것들과 벽을 싹다 날려버립시다. (큐 초기화, 큐에 검위치(현재지점) 넣어서 탐색 유도)

한층 깔끔해졌네요.
이제 BFS를 다시 돌려 검->종료지점 graph[N-1][M-1] 까지의 최단 거리를 구해주면 됩니다.

여기선 검에서 종료지점까지 최단거리는 4이며 최종적으로 공주를 구하는 최단거리는 10이겠네요.

---

출력

역시 골드문제는 허접 실버문제와는 차원이 다르게 출력조차 복잡합니다.
기억하실지 모르시겠지만 저희가 처음에 T라는 변수를 받았죠? 이 시간 안에 공주를 못구하면 무조건 Fail을 출력해야 합니다.

그리고 상단에 보시는 테스트케이스처럼 벽이 아예 막혀 구하러 가지 못할 경우도 고려해야 합니다.

if yes_gram == 0 or no_gram == 0:
    if yes_gram == 0 and no_gram != 0:
        if no_gram <= T:
            print(no_gram)
        else:
            print('Fail')
    elif yes_gram != 0 and no_gram == 0:
        if yes_gram <= T:
            print(yes_gram)
        else:
            print('Fail')
    else:
        print('Fail')

일단 둘 중에 하나라도 0이 있다면을 if문으로 만들어줍니다.
둘다 0이라면 벽에 막혀 아쉽게도 공주를 구하러 가지 못하므로 Fail을 출력해줍니다.

만약 하나만 0이라면 나머지 0이 아닌 값을 T와 대조해보고 T초 이하로 구하는게 가능하다면 해당 값을 출력합니다.
마찬가지로 T초 초과면 Fail을 출력해줍니다.

else:
    if min(yes_gram,no_gram) > T:
        print('Fail')
    else:
        print(min(yes_gram,no_gram))

만약 둘다 값이 0이 아니라면 더 작은 값과 T를 대조해서 T초 이하로 구하는 게 가능하다면 해당 값을, 아니면 Fail을 출력하면 끝납니다.

---

전체 코드

from collections import deque
import copy
dx = [0,0,-1,1]
dy = [1,-1,0,0]

def bfs_yesgram(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 
            if graph2[nx][ny] == 0:
                graph2[nx][ny] = graph2[x][y] - 1
                que.append([nx,ny])
            if graph2[nx][ny] == 2:
                graph2[nx][ny] = graph2[x][y] - 1

                for n in range(N):
                    for m in range(M):
                        if n != nx or m != ny:
                            graph2[n][m] = 0
                que.clear()
                que.append([nx,ny])
                break

    return graph2[N-1][M-1]

def bfs_nogram(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue 
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] - 1
                que.append([nx,ny])
    return graph[N-1][M-1]


N,M,T = map(int,input().split())
que = deque()
graph = []
for _ in range(N):
    graph.append(list(map(int,input().split())))
graph2 = copy.deepcopy(graph)

yes_gram = abs(bfs_yesgram(0,0))
no_gram = abs(bfs_nogram(0,0))


if yes_gram == 0 or no_gram == 0:
    if yes_gram == 0 and no_gram != 0:
        if no_gram <= T:
            print(no_gram)
        else:
            print('Fail')
    elif yes_gram != 0 and no_gram == 0:
        if yes_gram <= T:
            print(yes_gram)
        else:
            print('Fail')
    else:
        print('Fail')
else:
    if min(yes_gram,no_gram) > T:
        print('Fail')
    else:
        print(min(yes_gram,no_gram))

---

---