-
1261. [Python]알고스팟Python_알고리즘/Gold IV 2024. 3. 6. 20:25
1. 문제
https://www.acmicpc.net/problem/1261
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 다익스트라
- 우선순위 큐
3. 파이썬 코드
import heapq N,M = map(int,input().split()) matrix = [ list(map(int,input())) for _ in range(M) ] # 방향배열 탐색 direction = [(0,-1), (-1,0), (0,1), (1,0)] # 거리 값 갱신 distance = [ [10**9]*N for _ in range(M) ] def dijkstra(): # 시작 노드 설정 queue = [(1, (0,0))] # 시작 거리 1로 설정 distance[0][0] = 1 # queue 리스트 탐색 while queue: # 거리와 현재 노드 추출 dist, now = heapq.heappop(queue) # 거리가 현재 추출한 노드의 cost 값보다 작으면 반복문 다음걸로 if distance[now[0]][now[1]] < dist: continue # 방향배열 탐색 for k in range(4): ny = now[0] + direction[k][0] nx = now[1] + direction[k][1] # 범위안에 있으면 if 0 <= ny < M and 0 <= nx < N: # 벽이 아닌경우 if matrix[ny][nx] == 0: # 시작 값이 아니면 if distance[ny][nx] == 10**9: # 값 갱신 후 queue에 추가 distance[ny][nx] = dist heapq.heappush(queue,(dist,(ny,nx))) # 이미 값이 있으면 else: # 거리값 갱신 후 queue 에 cost, 노드 추가 if distance[ny][nx] > dist: distance[ny][nx] = dist heapq.heappush(queue,(dist,(ny,nx))) # 벽인 경우 else: # 벽을 부시면 기존의 cost에서 +1 한 값을 갱신 if distance[ny][nx] == 10**9: distance[ny][nx] = dist + 1 heapq.heappush(queue,(dist+1,(ny,nx))) dijkstra() print(distance[M-1][N-1]-1)
4. 문제를 풀고난 후 생각
- 다익스트라 문제에 방향배열까지 추가된 문제로 방향 탐색을 진행하며 벽인경우 cost 를 증가시키고 초기값인 경우 cost를 넣어주는 방식으로 문제에 접근했다.
- 기존의 값이 있는경우 더 작은 값으로 갱신해주는 방식으로 문제를 풀었고, 초기값이 1로 선언했으니 도착점에서 -1 을 출력해주면 최단거리를 알 수 있다.
- 기본적인 다익스트라 개념을 알고있으면 쉽게 접근이 가능한 문제다
5. 문제를 푸는데 도움이 되는 지식
- 우선순위 큐
- 다익스트
'Python_알고리즘 > Gold IV' 카테고리의 다른 글
9252. [Python]LCS 2 (0) 2024.06.20 1253. [Python] 좋다 (1) 2024.03.13 1753. [Python]최단경로 (0) 2024.03.03 17425. [Python]약수의 합 (1) 2023.10.09 9019. [Python]DSLR (1) 2023.10.08