악명 높은 DFS/BFS 문제이다.
프로그래머스 Lv.2 게임 맵 최단거리
문제 분석
최단거리 문제이다. 위의 경우 각각 11, -1이 정답이 되는 문제이다.
첫 번째 코드def solution(maps): dx,dy = [1,-1,0,0],[0,0,-1,1] x0,y0 = len(maps),len(maps[0]) visited = [[10001 for _ in range(y0)] for _ in range(x0)] visited[0][0] = 1 def dfs(x,y): for i in range(len(dx)): x1,y1 = x+dx[i],y+dy[i] if x1 in range(0,x0) and y1 in range(0,y0): if visited[x1][y1] > visited[x][y]: if maps[x1][y1] == 1: visited[x1][y1] = visited[x][y] + 1 dfs(x1,y1) dfs(0,0) if visited[-1][-1] == 10001: return -1 else: return visited[-1][-1] return 0
출력 결과를 보니, 방법론 자체는 문제가 없는 듯 하다.
첫 번째 아이디어
1. maps의 최대 크기가 100 by 100 matrix이므로 절대 나올 수 없는 숫자(10001)로 채운 visited 배열을 선언한다.
2.visited[0][0]에 1을 선언해준다.
3. dx, dy에 좌표가 상하좌우로 이동할 수 있는 방법을 선언한다.
4. x0, y0에 index의 끝값을 선언한다.
5. dfs 함수를 선언한다.
6. 새로 이동할 좌표로 x1, y1을 지정한다
6-1) 이때 이동할 좌표가 범위 내에 있고,
6-2) 넘어가려는 자리가 벽으로 막혀있지 않고 (maps[x1][y1]이 1이고)
6-3)visited[x1][y1]이visited[x][y]+1보다 크면(이때 큰 경우는 아직 방문 안한 100001이거나, 더 나쁜 경로로 갔거나)`7)
visited[x1][y1]에 이전 좌표의 값 + 1을 새로 저장해주고
8) 재귀함수를 호출하여 다음 좌표에 대해 시행한다.
가만, 포스팅을 하다보니 런타임 에러의 이유를 알것 같다.for i in range(len(dx)): x1,y1 = x+dx[i],y+dy[i] if x1 == x0 and y1 == y0: break이렇게 수정해준다면?
응 안돼 돌아가
두 번째 코드from collections import deque def solution(maps): dx,dy = [1,-1,0,0],[0,0,-1,1] x0,y0 = len(maps),len(maps[0]) visited = deque() visited.append((0,0)) while visited: x,y = visited.popleft() for i in range(len(dx)): x1,y1 = x+dx[i],y+dy[i] if x1 in range(0,x0) and y1 in range(0,y0): if maps[x1][y1] == 1: maps[x1][y1] = maps[x][y] + 1 visited.append((x1,y1)) if maps[-1][-1] == 1: return -1 else: return maps[-1][-1]
새로운 아이디어
이번에는deque / while을 이용해서 maps 배열을 직접 수정한다.
1. 초기 설정값은 이전과 같고, visited를deque로 선언한다.
2. visited의 초기값으로(0,0)을 부여해준다.
3.visited == True를 조건으로 하여 반복문을 만든다.
3-1) popleft로 현재 좌표를 꺼낸다(x,y)
3-2) 좌표를 dx,dy에 의해 이동한다.
3-3) 이동한 좌표(x1,y1)이 범위 내에 있고,maps[x1][y1]이 1이면
3-4)maps[x1][y1]을 이전 좌표의 값에 1을 더해준다문제 조건에 의해 maps[0][0]의 초기값은 당연히 1이다 다른 방법으로 주어진 경우, maps[0][0] = 1으로 임의 설정 해줘야 한다.3-5)
visited에(x1,y1)좌표를 다시 넣어준다. (재귀 실행)이 부분이 반복문의 break 역할을 한다. 만약 조건을 만족하지 않는다면 visited 배열에 아무것도 추가되지 않아서, 다음 반복문은 실행되지 않고 종료된다.
- 여기까지의 작업 결과로,
maps배열을 직접 수정하며 counting 하였고,
배열의 마지막 값([-1][-1]index)이 초기값(1)이면 return -1
그렇지 않다면 그 마지막 값이 곧 우리가 원하는 답이 된다.
일단 통과가 되었다.
어떤 차이점이 있는거지?
첫 번째 방법은dfs를 이용해서 푼 것이고
두 번째 방법은bfs를 이용해서 푼 것이다.도와줘 GPT
오.. 완벽하게 원하는 대답을 얻었다.
1. BFS는 큐/스택을 이용하기 때문에 메모리 부족 에러가 뜨지 않고, 일반적으로 DFS보다 더 빠르다.
2. 특히 최단 거리 문제에서는 BFS가 압도적인 성능을 보여준다. 최단 거리 문제라면 반드시 BFS를 사용하자!
3. 하지만, 항상 BFS가 빠른 것은 아니다! 깊이가 얕거나, 데이터의 크기가 작으면 DFS가 더 빠를 수도 있다.
4. DFS로만 구현 가능한 문제도 있고, 구현 자체는 DFS가 더 간단하다.
