[홀로 하는 코딩 공부] 공주님을 구해라!(Python)

백준

사용 언어: Python

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

17836번: 공주님을 구해라!

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 처음에는 아래와 같이 작성해보았다. 

import sys
from collections import deque
input = sys.stdin.readline

N, M, T = list(map(int, input().split()))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
graph = []
pos_gram = []
for i in range(N):
    tmp = list(map(int, input().split()))
    if 2 in tmp:
        pos_gram = [i, tmp.index(2)]
    graph.append(tmp)

MAX_VALUE = 100001
def bfs(dst_x, dst_y):
    que = deque()
    que.append([0, 0])
    visited = [[MAX_VALUE]*M for _ in range(N)]
    visited[0][0] = 0

    while que:
        cx, cy = que.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] != 1 and visited[nx][ny] == MAX_VALUE:
                    visited[nx][ny] = visited[cx][cy] + 1
                    que.append([nx, ny])
    return visited[dst_x-1][dst_y-1]

no_gram = bfs(N, M)
yes_gram = bfs(pos_gram[0]+1, pos_gram[1]+1) + abs((N-1)-pos_gram[0]) + abs((M-1)-pos_gram[1])
answer = min(no_gram, yes_gram)

if answer > T:
    print('Fail')
else:
    print(answer)

 

▶ 기본적인 bfs 유형이었어서 단번에 통과하였다. 

▶ MAX_VALUE 값을 100001라고 설정한 이유

  - N하고 M의 최대값이 100이라서 최대로 만들어질수 있는 칸의 값이 100*100=10000이기에 10001값부터는 나올 수 없는 값이다.

import sys
from collections import deque
input = sys.stdin.readline

N, M, T = list(map(int, input().split()))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
graph = []
pos_gram = []
for i in range(N):
    tmp = list(map(int, input().split()))
    if 2 in tmp:
        pos_gram = [i, tmp.index(2)]
    graph.append(tmp)

MAX_VALUE = 100001
def bfs():
    que = deque()
    que.append([0, 0])
    visited = [[MAX_VALUE]*M for _ in range(N)]
    visited[0][0] = 0

    while que:
        cx, cy = que.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] != 1 and visited[nx][ny] == MAX_VALUE:
                    visited[nx][ny] = visited[cx][cy] + 1
                    que.append([nx, ny])
    return visited

return_visited = bfs()
no_gram = return_visited[N-1][M-1]
yes_gram = return_visited[pos_gram[0]][pos_gram[1]] + abs((N-1)-pos_gram[0]) + abs((M-1)-pos_gram[1])
answer = min(no_gram, yes_gram)

if answer > T:
    print('Fail')
else:
    print(answer)

 

▶ 첫번째 푼 방식 vs 두번째 푼 방식

  - 처음에는 검을 잡냐 마냐에 따라 도착지점이 달라지기에 각각 탐색을 진행하였다. 

  (검을 안 잡게 되면 도착지점은 [N,M] / 검을 잡게 되면 도착지점은 [pos_gram[0], pos_gram[1]])

  - 그런데 그렇게 하게 되면 탐색을 두 번 하게 되기에 시간이 더 오래 소요된다.

  - 해당 문제 같은 경우에는 제일 끝 지점인 [N,M]의 최대 값이 100 밖에 안되서 문제가 안되지만 최대 값이 더 크게 되면 효율성에서 걸릴 수 밖에 없다.

  - 그래서 maps에 대해서 도착지점([N,M])까지 우선 탐색을 진행하며 각각의 칸에 해당 칸 까지 올 수 있는 거리 중 최소 값을 작성하면 return_visited라는 배열이 생성된다.

  - 그렇다면 도착 지점이 어디냐에 따라 return_visited에서 값을 가져오면 되니 시간이 더 단축되게 된다.

 

▶ 그 결과, 아래 처럼 4ms정도가 단축되었다. 크게 단축 된 것은 아니지만 maps 크기가 커지면 고려해야하는 부분이다. 

 

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.