🗂️ 문제
링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844
💡 접근법
최단거리를 구하기 위해 BFS를 사용한다.
이때 상하좌우로 이동하면서 맵을 탐색해야 한다. 따라서 변화량을 나타내는 dx와 dy 리스트를 생성한다.
초기 시작 위치를 (0, 0)으로 지정하고, 시작 위치에서부터 상하좌우로 탐색한다. 탐색하면서 조건문을 통해 맵을 벗어나지 않는지, 벽이 아닌지, 방문한 적이 없는지 확인한다.
위 조건을 모두 만족할 경우 방문 처리를 수행하고, 맵의 현재 위치에 거리를 업데이트한다.
모든 탐색을 마친 후 최종 도착지까지의 거리가 1이면 상대팀 진영에 도착하지 못한 경우이므로 -1을 리턴하고, 거리가 1이 아닐 경우 도착지까지의 최단 거리를 리턴한다.
😎 내 코드
from collections import deque
def solution(maps):
N = len(maps)
M = len(maps[0])
visited = [[False] * (M) for _ in range(N)]
dx = [1, -1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
def BFS():
queue = deque()
queue.append((0, 0))
visited[0][0] = True
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M: # 맵을 벗어나지 않는지 확인
if maps[nx][ny] and not visited[nx][ny]: # 맵이 벽이 아니면서 방문한 적 없는지 확인
visited[nx][ny] = True
queue.append((nx, ny))
maps[nx][ny] = maps[x][y] + 1 # 거리 업데이트
BFS()
if maps[N-1][M-1] == 1:
return -1
else:
return maps[N-1][M-1]
'Algorithm > Programmers' 카테고리의 다른 글
[해시] 프로그래머스 Lv2. 전화번호 목록 - Python (0) | 2024.05.17 |
---|---|
[DFS] 프로그래머스 Lv3. 네트워크 - Python (0) | 2024.05.15 |
[이분탐색] 프로그래머스 Lv4. 징검다리 - Python (0) | 2024.05.09 |
[이분탐색] 프로그래머스 Lv3. 입국심사 - Python (0) | 2024.05.07 |
[DP] 프로그래머스 Lv3. 정수 삼각형 - Python (0) | 2024.04.06 |