문제 핵심
1. n * m 크기의 maps가 주어지고 maps에서 0은 벽을 1은 길을 나타낸다.
2. 목표지점은 maps의 우측 하단 끝 지점이며 시작지점은 (1,1) 이다.
3. 캐릭터는 상하좌우로 움직일 수 있으며, 벽으로 이동하는 것은 불가능하다.
4. 목표지점에 도달하기 위해 최소한의 움직임을 구하기
첫 번째 방법
최단거리를 구하는 문제이기에 BFS탐색법을 사용했지만 시간 초과가 발생하였다..ㅎㅎ
def solution(maps):
w = len(maps) - 1
h = len(maps[0]) - 1
visit = []
going = [[0,0,1]]
while going:
now = going.pop(0)
x, y, count = now[0], now[1], now[2]
if x == w and y == h:
return count
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = x + dx
ny = y + dy
if 0 <= nx <= w and 0 <= ny <= h and [nx, ny] not in visit and maps[nx][ny] == 1:
going.append([nx, ny, count + 1])
visit.append([nx, ny])
return -1
기본적인 BFS 문제는 풀이방법이 비슷하다.
1. BFS문제면 이동할 때 사방팔방 다 이동하고 그 값을 저장하는 변수 필요 => 큐 사용
2. 위로 이동하고 좌우 옆으로 이동했을 때 해당 좌우가 방문했는지 저장하는 변수 필요 => 좌, 우, 상, 하 이동
1. 목표지점을 계산하기 위한 maps의 세로 길이와 가로 길이를 w ,h 로 정의
2. visit라는 방문한 지점을 담을 리스트 정의
3. going은 방문해야할 지점을 담을 리스트
4. now 는 현재 지점이고 x, y, count 는 현재 x, y좌표 및 이동 거리
5. 만약 목표지점일 경우 이동 거리를 리턴
6. dx, dy 에는 (1, 0), (-1, 0), (0, 1), (0, -1) 상하좌우 이동의 값을 넣고
7. 경계 및 벽에 막히지 않고, 방문한 지점이 아닐 경우 방문할 지점에 추가하고 방문한 지점에 추가
8. 모든 경로를 탐색후에도 만족하지 않으면 -1 리턴
그래서 뭐가 문제인가.. 알아봤는데 나는 방문한 지점을 담은 리스트 visit를 리스트로 사용했고 이 경우에서 방문 여부를 확인하는 로직인 not in을 사용할 경우 시간복잡도가 크게 상승한다는 얘기.. 이를 해결하기 위해 visit를 set로 선언하여 통과하였다.
두 번째 방법
def solution(maps):
w = len(maps) - 1
h = len(maps[0]) - 1
visit = set()
going = [[0,0,1]]
while going:
now = going.pop(0)
x, y, count = now[0], now[1], now[2]
if x == w and y == h:
return count
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = x + dx
ny = y + dy
if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visit and maps[nx][ny] == 1:
going.append([nx, ny, count + 1])
visit.add((nx,ny))
return -1
set 자료형의 경우 내부 해시테이블을 이용하여 포함여부를 확인할 때 리스트보다 빠른 속도로 확인이 가능하여 시간을 줄여 해결할 수 있었다.
세 번째 방법
뭔가 내가 쓴건 깔끔하지 않다고 해야하나.. 그래서 다른 사람 코드를 봤더니
going 리스트도 deque를 사용하여 속도를 더욱 줄이는 방법이 있고 깔끔했다.
from collections import deque
def solution(maps):
w = len(maps) - 1
h = len(maps[0]) - 1
visit = set()
going = deque([[0,0,1]])
while going:
now = going.popleft()
x, y, count = now[0], now[1], now[2]
if x == w and y == h:
return count
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx = x + dx
ny = y + dy
if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visited and maps[nx][ny] == 1:
going.append([nx, ny, count + 1])
visit.add((nx,ny))
return -1
deque를 사용하면 기존의 pop(), append()의 시간복잡도가 O(N)에서 popleft()를 통한 시간복잡도 O(1)로 줄어들기 때문에 n이 커질 경우 더욱 빠르게 문제해결이 가능해진다.
