8000 Python Sample Code Upload · euroversedev/Algorithm_Study@2ecc99e · GitHub
[go: up one dir, main page]
Skip to content

Commit 2ecc99e

Browse files
VSFeVSFe
committed
Python Sample Code Upload
1 parent b1204bd commit 2ecc99e

File tree

3 files changed

+114
-0
lines changed

3 files changed

+114
-0
lines changed

‎Concept/07_Graph_Traversal/Sample_Code/Python/1260.py

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
"""
2+
문제: DFS와 BFS (http://boj.kr/1260)
3+
Tier: Silver 2 (2021.01.14 기준)
4+
Comment: BFS와 DFS의 기본적인 활용법을 공부하는 문제입니다.
5+
딱히 어렵지는 않죠?
6+
"""
7+
8+
from collections import deque
9+
import sys
10+
11+
N, M, V = map(int, sys.stdin.readline().rstrip().split())
12+
13+
graph = [[] for _ in range(N + 1)] # 배열의 인덱스는 0부터 시작하지만 데이터는 1부터 시작합니다.
14+
visited = [False for _ in range(N + 1)]
15+
16+
def dfs(x, order: list):
17+
visited[x] = True
18+
order.append(x)
19+
for next in graph[x]:
20+
if not(visited[next]):
21+
dfs(next, order)
22+
23+
def bfs(start, order: list):
24+
q = deque()
25+
visited[start] = True
26+
q.append(start)
27+
order.append(start)
28+
29+
while(len(q)):
30+
node = q.popleft()
31+
for next in graph[node]:
32+
if visited[next]:
33+
continue
34+
visited[next] = True
35+
order.append(next)
36+
q.append(next)
37+
38+
39+
for _ in range(M):
40+
x, y = map(int, sys.stdin.readline().rstrip().split())
41+
graph[x].append(y)
42+
graph[y].append(x)
43+
44+
for i in range(N + 1):
45+
graph[i].sort()
46+
47+
dfsOrder = []
48+
bfsOrder = []
49+
dfs(V, dfsOrder)
50+
visited = [False for _ in range(N + 1)]
51+
bfs(V, bfsOrder)
52+
53+
print(*dfsOrder)
54+
print(*bfsOrder)

‎Concept/07_Graph_Traversal/Sample_Code/Python/2606.py

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
"""
2+
문제: 바이러스 (http://boj.kr/2606)
3+
Tier: Silver 3 (2021.01.14 기준)
4+
Comment: 1번을 기준으로 탐색해서 몇 군데를 방문했는지 출력하면 됩니다.
5+
"""
6+
7+
import sys
8+
9+
N = int(sys.stdin.readline().rstrip())
10+
M = int(sys.stdin.readline().rstrip())
11+
12+
graph = [[] for _ in range(N + 1)]
13+
visited = [False for _ in range(N + 1)]
14+
15+
for _ in range(M):
16+
x, y = map(int, sys.stdin.readline().split())
17+
graph[x].append(y)
18+
graph[y].append(x)
19+
20+
def dfs(x):
21+
visited[x] = True
22+
for next in graph[x]:
23+
if not(visited[next]):
24+
dfs(next)
25+
26+
dfs(1)
27+
print(sum(visited) - 1)

‎Concept/07_Graph_Traversal/Sample_Code/Python/2667.py

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
"""
2+
문제: 단지번호붙이기 (http://boj.kr/2606)
3+
Tier: Silver 1 (2021.01.14 기준)
4+
Comment: 배열을 그래프로 보고 해석해서 푸는 문제입니다.
5+
배열 내에서 이동하는 문제는 정말 많이 나오는 유형이니, 이 문제를 통해서 꼼꼼히 공부하면 좋을 것 같아요.
6+
"""
7+
8+
import sys
9+
10+
N = int(sys.stdin.readline().rstrip())
11+
graph = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
12+
dx = [1, -1, 0, 0]
13+
dy = [0, 0, 1, -1]
14+
visited = [[False for _ in range(N)] for _ in range(N)]
15+
component = []
16+
17+
def dfs(x, y, idx):
18+
visited[x][y] = True
19+
component[idx] += 1
20+
for i in range(4):
21+
X = dx[i] + x; Y = dy[i] + y
22+
if X < 0 or X == N or Y < 0 or Y == N:
23+
continue
24+
if not(visited[X][Y]) and graph[X][Y] == '1':
25+
dfs(X, Y, idx)
26+
27+
for i in range(N):
28+
for j in range(N):
29+
if not(visited[i][j]) and graph[i][j] == '1':
30+
component.append(0)
31+
dfs(i, j, len(component) - 1)
32+
33+
print(len(component), *sorted(component), sep = '\n')

0 commit comments

Comments
 (0)
0