백준_17836_공주님을 구해라!(python)

※ 접근법

 그래프가 주어지고 최소의 경우의 수를 구해야 하기에 bfs를 떠올렸다. n,m의 크기를 보고 그람을 사용하고 공주를 찾는 경우를 구하는 함수와 그람을 사용하지 않고 공주를 찾는 경우의 수를 동시에 구해야 시간초과가 나오지 않을 것이라 생각했다.

 

※ 풀이

1. 0,0부터 시작해 bfs를 시작한다.

2. 방문하지 않았고 배열 범위 안에 있는 조건을 만족하고 그 때 빈 공간이라면 큐에 추가한다.

3. 다음 좌표가 그람이 있는 곳이었다면 그람과 공주 사이의 좌표 거리를 계산한다.

 

※ 정답코드

from collections import deque

n,m,t = map(int,input().split())

data = [list(map(int,input().split())) for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]
gram_dist = float("inf")
min_result = float("inf")

def bfs(i,j,visited):
    global gram_dist
    q = deque()
    q.append((i,j))
    visited[i][j] = 0
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1:
                if data[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx,ny))
                if data[nx][ny] == 2:
                    gram_dist = ((n-1) - nx) + ((m-1) - ny) + visited[x][y] + 1
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx,ny))
                if nx == n -1 and ny == m - 1:
                    return min(visited[x][y] + 1, gram_dist)
    return gram_dist # 원래 -1이었는데 이렇게 바꿔주니 통과과 됐다. 이유가 뭘까....

visited = [[-1] * m for _ in range(n)]

min_result = bfs(0,0,visited)

if min_result > t:
    print("Fail")
else:
    print(min_result)

※ 회고

그람을 구하지 않고 공주에게 도달할 수 있는 경우의 수가 존재하는데 생각하지 못했다.  진짜 이유를 모르겠어서 맞왜틀??????이란 생각에 틀린 코드만 제출을 10번 했다. 틀린 데는 다 이유가 있으니 처음부터 다시 생각해보자