백준 1697
import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph = [0] * 100001
#M까지 완성
def BFS(index) :
q= deque([index])
cnt = 0
while q :
for i in range(M) :
cnt = cnt +1
for j in range(3**i) :
next = q.popleft()
if next == M :
return cnt -1
if 0<next<100001 and graph[next] == 0:
graph[next] = 1
q.append(next+1)
q.append(next-1)
q.append(next*2)
print(BFS(N))
보자마자 BFS를 생각해서 뿌듯한데.. 저번 풀이때 세부 내용은 기억하지 않으려 한게 큰 문제가 되어서 최종 정리를 해보려한다.
1. 최단 거리를 구하려면, BFS로 이동하면 그떄 처음 나오는 거리가 최단 거리이다.
2. 그러면 그 거리는? GRAPH에 이전 경로 +1을 해서 구한다. 중간 중간 3번 4번 도달하는 곳의 거리 값은 바뀌겠지만, 어차피 최종적으로 처음 나오는 거리시 바로 답이 나오니 상관 없다. (방문한 곳은 방문하지 않으면 된다)
** 그 이유는 bfs에서 방문한곳 방문은 돌아가는 것이기 때문
즉, for문으로 depth를 계산할 필요 없이 한번 도달하면 끝난다 생각하고 한번 도달하면 이전 거리에서 더하기만 하면 되었던것.
import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph = [0] * 100001
#M까지 완성
def BFS(index) :
q= deque([index])
cnt = 0
while q :
next = q.popleft()
if next == M :
return graph[next]
for x in (next-1,next+1,next*2) :
if 0<=x<= 100000 and graph[x] == 0 :
graph[x] = graph[next]+1
q.append(x)
print(BFS(N))
기억하자 -
BFS로 최단 거리까지의 최소 경로를 구할때는, 한번 도달한 경로가 최종 최소 경로가 된다고 생각하면 된다.
(다시 도달하지 못하게 해도 상관없다, 어차피 처음 나온 값에 대한 경로가 최단 경로이다.)
(DEPTH를 계산하거나 할 필요가 없다.)
*가는데 걸리는 비용(DEPTH)를, VISITED에 저장하는 이 형태를 기억하자
++최단거리 외 1문제 추가
백준 2606
import sys
sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
forloop = 0
graph = [[]for _ in range(N+1)]
visited = [False] * (N+1)
while forloop < M :
x,y = map(int,sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
forloop += 1
noagainarray = []
def DFS(index) :
visited[index] = True
for i in graph[index] :
if visited[i] == False:
#아직안갔으면
if i not in noagainarray :
noagainarray.append(i)
DFS(i)
return
DFS(1)
print(len(noagainarray))
변수명을 보면 알겠지만, 쉽게 풀었다.
해당 내용을 작성하는 이유는, 현재는 한번이라도 방문하면 그 곳의 정보를 모두 저장하기 때문에
쉽게 풀었지만. 만약 모든 단말노드까지의 경로를 탐색하고 싶다면
def DFS(index) :
visited[index] = True
for i in graph[index] :
if visited[i] == False:
#아직안갔으면
DFS(i)
visited[i] = False
return
이렇게하면 단말 노드까지 모든 경로를 탐색한다.