https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제설명
링크 참고
문제 해결 방법
bfs를 통해 문제를 해결하였음
코드 구현
과거에 작성한 코드
더보기
from collections import deque
def solution(maps):
answer = 0
# map은 2차원 배열이라고 생각하면 됨
n = len(maps) #가로
m = len(maps[0]) #세로
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0] #세로축
dy = [0, 0, -1, 1] #가로축
def bfs(x,y):
#큐 구현을 위해 deque라이브러리 사용
queue = deque()
queue.append((x,y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if maps[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래 까지의 최단 거리 반환
return maps[n-1][m-1]
if bfs(0,0)==1:
answer=-1
else:
answer=bfs(0,0)
return answer
from collections import deque
def solution(maps):
answer = 0
n = len(maps)
m = len(maps[0])
# 최단 거리 구하기.
# bfs - deque
# 1,1 부터 시작
dx = [1, -1, 0, 0] # 동, 서, 남, 북
dy = [0, 0, -1, 1]
# 게임 맵 벗어난 길은 갈 수 없음
queue = deque([(0, 0)])
distance = 0
visited = [[False] * n for _ in range(m)]
visited[0][0] = True
while 1:
if len(queue) == 0:
break
x, y = queue.popleft()
if x == n-1 and y == m-1:
check = 1
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= n or ny >= m or nx < 0 or ny < 0:
continue
if maps[nx][ny] == 0:
continue
if maps[nx][ny] == 1:
queue.append([nx, ny])
maps[nx][ny] = maps[x][y] +1
answer = maps[n-1][m-1]
if answer == 1:
return -1
return answer
시간/공간 복잡도
O(N*M)
최적화 및 개선
.
어려웠던 점
가로 세로가 헷깔렸음.
예전에 풀어봤던 문제인데도 처음엔 느낌조차 없다가 점점 느낌 살아났지만, 예전에 고민했던 부분을 또 고민하며 문제를 풀었다.
'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [프로그래머스 lv3] 배달 (1) | 2024.04.10 |
|---|---|
| [프로그래머스 lv3] 네트워크 (0) | 2024.04.10 |
| 벨만포드 알고리즘 (0) | 2024.04.09 |
| 다익스트라 알고리즘 (0) | 2024.04.08 |
| BFS 순회 (0) | 2024.04.08 |