[백준 31946번 알고리즘] 죽음의 등굣길 파이썬 풀이

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

백준 31946번 문제

 

 

우선 bfs에 익숙하지 않은 분들은 아래 두 문제를 우선 풀이해보는것을 추천드립니다.

https://coldmans.tistory.com/1

백준 1697번 숨바꼭질 문제 bfs 파이썬 풀이

https://coldmans.tistory.com/5

[백준 1931번 알고리즘] 회의실 배정 파이썬 풀이

이 문제 또한 bfs풀이를 목적으로 두고있습니다.

 

우선 조건들을 따져보겠습니다.

DEAD가 되는 경우들을 따져봐야하겠죠?

 

 

출발과 도착이 다름

예시를 위해 N과 M이 모두 6인 경우를 가정해서 설명하려고 합니다.

이 경우는 출발 지점과 도착 지점이 달라서 무조건 DEAD하는 경우입니다.

 

거리가 모자름

두번째로는 X에 비해 거리가 멀리 떨어져있으면 발생하는 경우 입니다.

X가 3일때 이동을 해야하는데 이 경우는 출발지에서 가장 가까운 지점이 5만큼 떨어져있어 이동을 못해 DEAD입니다.

 

 

거리 계산은 간단합니다. 이동하려는 좌표의 x차이와 y차이를 더했을때 기존에 점프력이라고 입력된 X보다 작거나 같으면 이동이 가능합니다.

 

엇? 그동안 풀어본 bfs문제들은 주어진 거리만큼만 이동만 했는데 이건 거리안에 있는 값이면 모두 이동할 수 있다는거네요?

 

그럼 X가 3인경우 이동할때 이런식으로 이동이 가능하겠네요? 마지막점에 도달할때는 1밖에 이동하지 않지만 결국 점프력이 3이니까 충분하다는거죠?

 

 

그럼 머리로는 이해했는데 어떤 식으로 코드를 짜야할까요?

 

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

n = int(input().strip())
m = int(input().strip())

graph = [[int(x) for x in input().strip().split()] for _ in range(n)]
wax = graph[0][0]

visited = [[-1 for _ in range(m)] for _ in range(n)]
x = int(input().strip())
if graph[0][0] != graph[n-1][m-1]:
    print("DEAD")
    sys.exit()
q = deque()
q.append((0,0))
visited[0][0] = 1

while q:
    a,b = q.popleft()
    for dy in range(-x,x+1):
        for dx in range(-x,x+1):
            if abs(dy) + abs(dx) <= x:
                se = dy + a
                ga = dx + b
                if (0 <= se < n) and (0 <= ga < m): 
                    if (graph[se][ga] == wax) and (visited[se][ga] == -1):
                        if (se == n-1) and (ga == m-1):
                            print("ALIVE")
                            sys.exit()
                        visited[se][ga] = 1
                        q.append((se,ga))
print("DEAD")

 

wax = graph[0][0]
visited = [[-1 for _ in range(m)] for _ in range(n)]
x = int(input().strip())

 

출발지점의 색깔을 저장하고 visited배열을 만들어줍니다.

 

if graph[0][0] != graph[n-1][m-1]:
    print("DEAD")
    sys.exit()

이 부분이 처음 색깔과 마지막 색깔이 다르면 DEAD를 출력하고 바로 프로그램을 종료해주는 코드입니다.

 

while q:
    a, b = q.popleft()
    for dy in range(-x, x+1):
        for dx in range(-x, x+1):
            if abs(dy) + abs(dx) <= x:
                se = dy + a
                ga = dx + b
                if (0 <= se < n) and (0 <= ga < m):
                    if (graph[se][ga] == wax) and (visited[se][ga] == -1):
                        if (se == n-1) and (ga == m-1):
                            print("ALIVE")
                            sys.exit()
                        visited[se][ga] = 1
                        q.append((se, ga))
print("DEAD")

 

이 부분에서 일반적인 dfs문제와 다른점이 나옵니다. for문을 2중으로 돌려 범위 내에 이동할 수 있는 점을 전부 탐색해줘야합니다. 이때 -x부터 돌려야지 왼쪽에 있는 점도 탐색할 수 있기때문에 -x부터 돌립니다.

 

 

새 위치가 도착지점 (n-1, m-1)이면 "ALIVE"를 출력하고 프로그램을 종료합니다.

 

마지막으로 

모든 탐색을 마친 후에도 도착지점에 도달하지 못하면 "DEAD"를 출력합니다.

 

이해가 되지않거나 어려운 부분이 있다면 댓글 남겨주시면 설명 보충하겠습니다. 감사합니다. coldmans였습니다.

매일 한문제씩 알고리즘 문제를 풀고 싶은 분은 구독해주시면 감사하겠습니다.