문제 출처 : https://www.acmicpc.net/problem/2178
한 한시간 정도 걸려서 풀은 것 같다... (이것도 장족의 발전입니다ㅜㅜ)
불과 두달 전만 해도 알고리즘 자체에 대해서도 전무후무 그냥 문자열? 관련 문제들 같은것만 풀고 간단한 구현문제들만 시도했는데 나름 그래도 이제 구박사님의 도움없이 알고리즘을 스스로 짤 수 있다는 것에 스스로에게 박수를 보낸다 하핫 ( 물론 기초적인 문제지만... )
사고 과정
BFS를 이용하자고 결정. ( 이유는 뒤에 )
1. BOARD위에 나의 위치를 기반으로 동서남북, 모든 방향을 탐색하자
-> 처음에는 INDEX를 그냥 변수로 직접 줄라했느데 반복되는 코드 라인들이 보여서 dic이라는 방향 변수를 이용하여 for문으로 처리해줬다.
2. 지나간 곳은 VISITED 처리를 해줘야 한다 ( 여기서 잠깐! 과연 지나간 길을 다시 지나가면서 최단 거리일 수 있을까? 결과는 불가능. )
-> 그래서 지나간 자리는 이동할 수 없는 0과 같은 취급을 하여 0으로 변경해준다.
3. 목적지에 도착하면 if문으로 종료시킨다...될까?
-> BFS니까, height( 이동한 거리 ) 단위로 그래프를 탐색하니까 결국 최단 거리로 이동하여 목적지에 도달했을 때 가장 빨리 도착한다.
3단계에서 약간 실수가 있었다. 위치(pos)가 바뀔때마다 처음에는 count를 해줬는데 이렇게 될 경우
결과는 1->3->F 로 3이 되어야 하는데 1->2->3->F로 4가 되버린다.
그렇기 때문에 트리에서의 HEIGHT의 개념을 바탕으로 여기에 이동한 거리라는 걸 적용시킨다. 이를 구현하기 위해 tmp (해당 height에 있는 node의 수 ), next_tmp( next height에 있는 node의 수 ), height라는 변수를 도입하여 한 height에 있는 node를 조회할 때마다 next_tmp에 값을 추가해주고 que에서 tmp만큼 pop된다면 해당 height의 모든 node들을 조회했다 판단. tmp=next_tmp로 해주고 height+1을 해주어 다음 height로 넘어간다.
어떤 최단 경로, 특수한 경로를 구할 때는 DFS보다 BFS가 훨씬 유리하다. 그 이유를 대략적으로 짐작해보면 이렇지 않을까? DFS로 구현할 경우 해당 경로가 아니라면 다시 다른 경로를 탐색하고 문제의 경우까지 모두 탐색을 해야하다보니 '통상적으로' 시간 복잡도가 커지게 되는 것이다.
import sys
from collections import deque
N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
board = [[0 for f in range(M+2)]]+[[0]+list(map(int,sys.stdin.readline().rstrip("\n")))+[0] for m in range(N)]+[[0 for l in range(M+2)]]
h,w = 1,1
pos = deque([[h,w]])
board[pos[0][0]][pos[0][1]]=0
dic = [[0,1],[1,0],[0,-1],[-1,0]]
height, tmp, next_tmp = 0, 1, 0
while pos :
#동,남,서,북
now=pos.popleft()
tmp-=1
if (now[0]==N) and (now[1]==M) :
print(height+1)
break
#코드 동일 recycle
#결국 몇번째 height냐 => 정답
for i in range(4) : # 0,1,2,3
if board[now[0]+dic[i][0]][now[1]+dic[i][1]] == 1 :
pos.append([now[0]+dic[i][0],now[1]+dic[i][1]])
board[now[0]+dic[i][0]][now[1]+dic[i][1]]=0
next_tmp+=1
if tmp==0 :
tmp = next_tmp
next_tmp = 0
height+=1결과는 맞았지만 실행시간이 다른 사람들에 비해 평균적으로 더 오래 걸리기 때문에 과연 어떻게 푸는 게 더 효율적인가 공부해보자.
! 혼자 공부를 위해 참고하고자 적어놧지만 문제가 된다면 삭제하겠습니다.
- dllwoans0001님의 풀이 : 나는 다음 레벨( 이동 거리 )로 넘어가는 것을 고려하기 위해 모든 노드들을 조회하는 것에 대해 변수를 직접 적용해서 카운팅하여 계산했다. 왜냐하면 노드들을 조회하고 이동가능할 경우 deque에 추가 되기때문에 노드의 수만큼 deque에 추가되기 때문이다. 이 분은 모든 노드를 조회한다를 set이라는 개념을 이용하여 풀이하셨다. set에는 어떤 위치에서 갈 수 있는 다음 위치들(A)이 모두 저장된다. 1회돌고 나서 set에는 다시 A에서 갈 수 있는 모든 위치들(B)이 저장된다. 이렇게 deque에 얽매이지 말고 구현하고자 하는 기능에 맞춰 적절한 함수, 자료구조등을 생각할 수 있는 능력을 길러야 할 것 같다.
- deque를 이용한 다른 방법
1) board 와 같은 크기에 count 리스트를 만들어 이동할 경우 이전 이동경로+1을 해준다. ( 이전 값을 기반으로 다음 값이 결정, DP)
2) 공통적으로 한 height의 모든 NODE를 조회한 후에 height+1을 해줄수있다. 이때 조회하는 방식에 차이가 존재. 나는 while문은 한 노드를 기준으로 확인하고 이를 체크해주는 변수들을 따로 만들었고 어떤 사람은 while문 안에 노드에 link된 모든 node들을 탐색하는 for문을 또 만들어줘서 while문이 끝나기 전에 모든 노드를 조회하고 height+1을 해줄 수 있다.
