구름톤 챌린지 Week 3 - Day 14
구름톤 챌린지 3주, 14일차 문제 작은 노드이다.
그래프를 구현할 줄 알고, 약간의 논리적 사고가 가능하다면 풀 수 있는 문제이다.
코드에 들어가기 전에 문제 해석을 해보자.
'한 번 방문한 노드는 다시 방문할 수 없으며, 번호가 가장 작은 노드로 이동'한다.
이는 DFS와 BFS 중 DFS로 문제를 구현하라는 뜻이다.
# ---------- Import ----------
import sys
sys.setrecursionlimit(2002)
# ---------- Function ----------
def DFS(graph, v, visited):
global last_node
visited[v] = True
last_node.append(v)
for i in graph[v]:
if not visited[i]:
DFS(graph, i, visited)
return
# ---------- Main ----------
node, edge, start = map(int, input().split())
graph = [[] for _ in range(node+1)]
visited = [False] * (node+1)
for _ in range(edge):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(node+1):
graph[i].sort()
last_node = []
DFS(graph, start, visited)
print(sum(visited), last_node[-1])주의할 점을 나열해보자.
1. BFS가 아니라 DFS 그래프 구현이다.
2. 그래프를 이루는 간선은 양방향 간선이다.
3. 이동할 수 있는 노드가 없을 때, 그대로 종료한다.
4. 노드의 개수는 최대 2000개로, 재귀에 조심하자.
5. si, ei 입력에 속지말자. 오름차순으로 들어온다는 보장이 없다.
# ---------- Import ----------
import sys
sys.setrecursionlimit(2002)DFS로 구현한다는 말은 재귀 함수를 사용한다는 말과 동일하다.
노드 최대 개수는 2000개로, 최악의 경우 인접 행렬로 구현한다면 2000 * 2000 = 4,000,000의 탐색을 할 수도 있다.
따라서 최소 4백만의 한도를 갖게끔 제한을 풀어줘야 한다.
인접 리스트의 경우, 노드 최대 개수는 2000이므로 2000으로 풀어주면, 안 된다.
sys.setrecursionlimit(N)의 정확한 의미는, Python의 stack 공간을 N만큼 설정하라는 의미이다.
이때 main 함수 자체도 stack 공간에 쌓이게 된다.
즉, main에서 하나, 호출할 때 하나씩 차지하게 되므로 2000번째 노드를 검사하기 위해서는 2002만큼 공간이 필요하다.
메모리 저장과 Heap, stack 공간에 대한 개념을 모른다면 따로 공부하자.
빠듯하게 선언을 해서 2002로 한 것이지, 여유롭게 3000, 5000, 1000000으로 해도 상관은 없다.
하지만 그만큼 공간을 차지하기에, 자신이 구현하려는 방법(인접 행렬, 인접 리스트)과 상황에 따라 맞게 선언하자.
왼쪽은 인접 리스트 방식으로 노드와 간선 값이 있을 때, 탐색 순서대로 출력하는 기본 코드이다.
그리고 오른쪽의 코드는 구름톤 챌린지에서 사용하는 DFS 코드이다.
다른 점은? print() 대신 노드를 last_node에 추가했다는 것과 return의 유무 뿐이다.
마지막으로 검사를 한 지점에서 빠져나와야 하기에, 모든 공간을 다 탐색한 뒤에는 돌아갈 필요없이 return하면 된다.
# ---------- Main ----------
node, edge, start = map(int, input().split())
graph = [[] for _ in range(node+1)]
visited = [False] * (node+1)DFS와 BFS를 구현하는 방법에는 인접 행렬과 인접 리스트 방법이 있다.
인접 행렬은 N * N 크기의 공간을 선언해서, 존재하는 간선만 1로 초기화하는 방법이다.
인접 리스트는 빈 2차원 공간을 선언해서, 인접한 노드 값으로 초기화하는 방법이다.
graph는 인접 리스트용으로 초기화했고, visited는 방문 여부를 확인하는 list이다.
# ---------- Main ----------
for _ in range(edge):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)양방향 간선이기 때문에 [a] = b도 넣고, [b] = a도 넣어줘야 한다.
# ---------- Main ----------
for i in range(node+1):
graph[i].sort()처음에 주의했듯이, 순서대로 들어오는 것이 아니다.
1 6, 1 4로 들어오고 이를 그대로 실행한다면 4보다 6을 먼저 탐색할 것이다.
따라서 각 항목에 대해서 정렬을 해줘야 한다.
이 방법이 싫다면 인접 행렬을 사용하면 된다.
# ---------- Main ----------
last_node = []
DFS(graph, start, visited)
print(sum(visited), last_node[-1])visited는 0과 1로만 이루어진 list이다. visited를 다 더하면 방문한 노드 개수가 된다.
마지막으로 방문한 노드들을 추가할 last_node를 선언한다.
방문한 노드들을 순서대로 담고, 마지막에 return으로 빠져나오면 마지막 요소([-1])가 마지막 탐색 노드이다.