1 minute read

문제

접근 방법

이 문제는 다른 최소 거리 구하는 문제와 다르게 최소 방향 전환 횟수를 구해야 한다. 즉, 거리는 신경쓰지 말고 오직 방향 전환 횟수만 신경쓰면 된다.

생각한 방법은 dijkstra에서 보통 시작점에서 거리가 가장 짧은 노드를 먼저 조사하기 위해 priority queue의 우선순위를 거리로 하는데 이 우선순위를 방향 전환 횟수로 하는 것이다.

시작점에서 다른 지점들까지 이동하는데 걸린 최소 방향 전환 횟수를 구하면서 dijkstra를 하면 목적지까지 가는데 필요한 최소 방향 전환 횟수를 얻을 수 있다.

이때, 이동하기로 한 방향을 정했을 때 그 방향으로 가능할 때까지 이동하면서 계속 dijkstra를 진행해야 한다는 것이다. 그렇지 않으면 그 지점에 갔을 때 사용힌 방향 정보까지 저장하면서 dijkstra를 해야하는데 이 방법은 너무 복잡하다… 또, 한 방향으로 이동했을 때, 그 방향에 있는 지점들의 방향 전환 횟수는 모두 동일하기 때문에 이렇게 처리하는 것이 더 효율적이다.

정답 코드

`` python

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

””” 구하는 것은 최단 거리가 아니라 최소 방향 전환 횟수이다.

priority queue의 우선순위를 방향 전환 횟수로..? “””

w,h = map(int, input().split())

start_h, start_w, dest_h, dest_w = 0,0,0,0 maps = []

first = False

for l in range(h): line = list(input().rstrip()) maps.append(line) for i in range(w): #시작점이랑 목적지 구하기 if line[i] == ‘C’: if first: dest_h, dest_w = l, i else: start_h, start_w = l, i first = True

moves = [(0,1), (0,-1), (1,0), (-1,0)]

def dijkstra(): q = [] heapq.heappush(q,(-1, start_h, start_w)) #첫 이동은 방향 전환으로 count 하지 않도록 -1로 시작 nums_change = [[int(1e9)]*w for _ in range(h)] #최소 거리가 아니라 최소 방향 전환 횟수를 저장 nums_change[start_h][start_w] = 0

while q: mid_change, mid_h, mid_w = heapq.heappop(q)

#이미 방문했다면 skip
if nums_change[mid_h][mid_w] < mid_change:
  continue
  
for dh,dw in moves:
  end_h, end_w = mid_h+dh, mid_w+dw
  # 가는 방향을 정했을 때, 그 방향으로 쭉 가면서 각 지점까지 가는데 걸리는 최소 방향 전환 횟수를 저장함
  while 0<=end_h<h and 0<=end_w<w and maps[end_h][end_w] != '*':
    new_change = mid_change+1
    if new_change < nums_change[end_h][end_w]:
      nums_change[end_h][end_w] = new_change
      heapq.heappush(q, (new_change, end_h, end_w))
    #끝에 도달할 때까지 한 방향으로 계속 이동
    end_h+=dh
    end_w+=dw

return nums_change

mirrors = dijkstra() print(mirrors[dest_h][dest_w])

```

You May Also Enjoy