코드

import heapq

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

graph =[]
    
for _ in range(n):
    graph.append(list(map(int, input())))

# 좌표별 방문 여부를 체크할 리스트
visited = [[False for _ in range(m)] for _ in range(n)]

# 로직 구현
def solution():
    q = []
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # (벽을 부순 개수, x, y)
    # 일반적인 다익스트라와는 다르게 
    # 벽을 부순 개수로 가중치를 계산함
    heapq.heappush(q, (0, 0, 0))
    
    # 시작점 방문 처리 
    visited[0][0] = True
    
    while heapq:
        cnt, x, y = heapq.heappop(q)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            # (n,m)에 도착
            # 함수 종료
            if x == n-1 and y == m-1:
                print(cnt)
                return

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if not visited[nx][ny]:
                visited[nx][ny] = True

                # 벽인 경우
                if graph[nx][ny] == 1 :
                    
                    # 벽을 부수고 전진하므로 cnt+1
                    heapq.heappush(q, (cnt+1, nx, ny))
                else:
                    heapq.heappush(q, (cnt, nx, ny))
                
            
solution()

문제 해설

우선 순위 큐를 활용한 문제.

문제의 분류가 다익스트라 알고리즘에 있는 문제이나, 이 때까지 흔하게 풀던 패턴의 문제는 아니었다.

기존에 접했던 문제들과 달리 이 문제는 마지막 좌표까지 가는 최단 거리가 아닌, 어떻게 가든 부수는 벽의 개수를 최소화시키는 경우를 구하라는 것이 문제의 요지.

즉, 최단 경로를 구하는 다익스트라 알고리즘이나 미로 탈출에 적용하는 BFS를 간단하게 사용해서 풀 수 있는 문제가 아니었다.

혼자서 고민하였으나 별 다른 해결책을 생각하지 못하여 결국 구글링을 참고하였고, 이를 토대로 알게 된 풀이 방법은 생각보다 어렵지 않았다.

다익스트라 알고리즘에서 사용하던 heapq를 그대로 사용하는데 (아마 이 부분때문에 다익스트라 알고리즘에 분류돼있는 것 같음), 가중치를 소요 시간이 아닌 벽을 부순 개수로 선정하여 우선 순위 큐에 넣어주는 방식으로 문제를 해결한다. 또한 BFS에서 사용하던 다음 노드로 가는 방향 리스트를 활용하여 그래프 전체를 탐색하면서 최종 좌표 (n, m)에 도착한다. 이 때, 우선 순위 큐의 특성상 heapq.heappop을 수행하면 가중치로 선택한 cnt의 값이 가장 작은 튜플이 pop되므로 이 값을 출력하면 정답으로 인정된다.

어떤 알고리즘이든 기본 유형을 벗어난 문제를 마주하게 되면 문제 자체가 완전히 새롭게 느껴져서 힘든 것 같다… ㅠㅠ 결국 이 부분은 정말 많은 문제를 통해 다양한 유형을 접하면서 극복해 나가야 하는 부분이다. 열심히 노력하여 어떤 문제든 겁먹지 않고 풀 수 있는 실력을 갖추겠다.

댓글남기기

참고