Python Sample Code Upload

VSFe · VSFe · commit 2ecc99ec055f · 2021-01-14T10:30:13.000+09:00
diff --git a/Concept/07_Graph_Traversal/Sample_Code/Python/1260.py b/Concept/07_Graph_Traversal/Sample_Code/Python/1260.py
@@ -0,0 +1,54 @@
+"""
+문제: DFS와 BFS (http://boj.kr/1260)
+Tier: Silver 2 (2021.01.14 기준)
+Comment: BFS와 DFS의 기본적인 활용법을 공부하는 문제입니다.
+딱히 어렵지는 않죠?
+"""
+
+from collections import deque
+import sys
+
+N, M, V = map(int, sys.stdin.readline().rstrip().split())
+
+graph = [[] for _ in range(N + 1)] # 배열의 인덱스는 0부터 시작하지만 데이터는 1부터 시작합니다.
+visited = [False for _ in range(N + 1)]
+
+def dfs(x, order: list):
+    visited[x] = True
+    order.append(x)
+    for next in graph[x]:
+        if not(visited[next]):
+            dfs(next, order)
+
+def bfs(start, order: list):
+    q = deque()
+    visited[start] = True
+    q.append(start)
+    order.append(start)
+
+    while(len(q)):
+        node = q.popleft()
+        for next in graph[node]:
+            if visited[next]:
+                continue
+            visited[next] = True
+            order.append(next)
+            q.append(next)
+
+
+for _ in range(M):
+    x, y = map(int, sys.stdin.readline().rstrip().split())
+    graph[x].append(y)
+    graph[y].append(x)
+
+for i in range(N + 1):
+    graph[i].sort()
+
+dfsOrder = []
+bfsOrder = []
+dfs(V, dfsOrder)
+visited = [False for _ in range(N + 1)]
+bfs(V, bfsOrder)
+
+print(*dfsOrder)
+print(*bfsOrder)
diff --git a/Concept/07_Graph_Traversal/Sample_Code/Python/2606.py b/Concept/07_Graph_Traversal/Sample_Code/Python/2606.py
@@ -0,0 +1,27 @@
+"""
+문제: 바이러스 (http://boj.kr/2606)
+Tier: Silver 3 (2021.01.14 기준)
+Comment: 1번을 기준으로 탐색해서 몇 군데를 방문했는지 출력하면 됩니다.
+"""
+
+import sys
+
+N = int(sys.stdin.readline().rstrip())
+M = int(sys.stdin.readline().rstrip())
+
+graph = [[] for _ in range(N + 1)]
+visited = [False for _ in range(N + 1)]
+
+for _ in range(M):
+    x, y = map(int, sys.stdin.readline().split())
+    graph[x].append(y)
+    graph[y].append(x)
+
+def dfs(x):
+    visited[x] = True
+    for next in graph[x]:
+        if not(visited[next]):
+            dfs(next)
+
+dfs(1)
+print(sum(visited) - 1)
diff --git a/Concept/07_Graph_Traversal/Sample_Code/Python/2667.py b/Concept/07_Graph_Traversal/Sample_Code/Python/2667.py
@@ -0,0 +1,33 @@
+"""
+문제: 단지번호붙이기 (http://boj.kr/2606)
+Tier: Silver 1 (2021.01.14 기준)
+Comment: 배열을 그래프로 보고 해석해서 푸는 문제입니다.
+배열 내에서 이동하는 문제는 정말 많이 나오는 유형이니, 이 문제를 통해서 꼼꼼히 공부하면 좋을 것 같아요.
+"""
+
+import sys
+
+N = int(sys.stdin.readline().rstrip())
+graph = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
+dx = [1, -1, 0, 0]
+dy = [0, 0, 1, -1]
+visited = [[False for _ in range(N)] for _ in range(N)]
+component = []
+
+def dfs(x, y, idx):
+    visited[x][y] = True
+    component[idx] += 1
+    for i in range(4):
+        X = dx[i] + x; Y = dy[i] + y
+        if X < 0 or X == N or Y < 0 or Y == N:
+            continue
+        if not(visited[X][Y]) and graph[X][Y] == '1':
+            dfs(X, Y, idx)
+
+for i in range(N):
+    for j in range(N):
+        if not(visited[i][j]) and graph[i][j] == '1':
+            component.append(0)
+            dfs(i, j, len(component) - 1)
+
+print(len(component), *sorted(component), sep = '\n')
