Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 그래프 이론
- 그리디
- 에라토스테네스의 체
- DP
- DFS
- 다이나믹 프로그래밍
- 트리
- MST
- 누적합
- 다시
- 우선순위큐
- 자료구조
- 브루트포스
- GROUP BY
- 크루스칼
- 다이나믹프로그래밍
- 투포인터
- 수학
- 재귀
- 서브쿼리
- BFS
- 플로이드-워셜
- 다익스트라
- join
- 시뮬레이션
- 그래프 탐색
- 해시
- 백트래킹
- 구현
- 분할정복
Archives
- Today
- Total
기록하고 까먹지 말기
게임 맵 최단거리 본문
날짜 : 2023. 09. 28
사용 언어 : python
문제



코드
from collections import deque
def solution(graph):
n, m = len(graph), len(graph[0])
for i in range(n):
for j in range(m):
if graph[i][j] == 1: graph[i][j] = 0
else: graph[i][j] = 1
answer = 0
queue = deque()
queue.append([0, 0])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while queue:
x, y = queue.popleft()
if x == (n-1) and y == (m-1):
return graph[x][y] + 1
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx in range(n) and ny in range(m): # 범위 확인
if (nx, ny) != (0, 0) and graph[nx][ny] == 0: # 방문여부 체크
graph[nx][ny] = graph[x][y] + 1
queue.append([nx, ny])
return -1
풀이
- 일반적인 BFS로 풀이하는 문제였다.
- 따로 방문여부를 저장하는 리스트를 만들지 않고, 이동 가능한 칸은 0, 벽은 1로 하되, 이동한 거리를 저장하도록 움직일 때마다 해당 좌표에 가산하는 방식으로 큐를 돌렸다.
- 다만 문제의 조건에서 1이 이동 가능한 칸, 0이 벽으로 제시되었기 때문에 문제 처음에 1을 0으로, 0을 1로 변환하는 작업을 실시하였다.
알게된 점
-
참고 사이트
-
'전공 > 프로그래머스' 카테고리의 다른 글
(SQL) 중성화 여부 파악하기 (0) | 2023.10.01 |
---|---|
(SQL) 자동차 평균 대여 기간 구하기 (0) | 2023.10.01 |
(SQL) 조건에 맞는 사용자와 총 거래금액 조회하기 (0) | 2023.09.28 |
124나라의 숫자 (0) | 2023.09.26 |
이진 변환 반복하기 (0) | 2023.09.25 |