EDOC 2023-2 5주차 과제

05-1. 깊이 우선 탐색

 

023. 연결 요소의 개수 (백준 11724번)

 

https://www.acmicpc.net/problem/11724

 

from sys import stdin
import sys

sys.setrecursionlimit(10000)

n, m = map(int, stdin.readline().split())
data = [[] for i in range(n)]
visited = [False] * n

def DFS(v):
    visited[v] = True
    for i in data[v]:
        if not visited[i-1]:
            DFS(i-1)

for i in range(m):
    a, b = map(int, stdin.readline().split())
    data[a-1].append(b)
    data[b-1].append(a)

count = 0

for i in range(n):
    if not visited[i-1]:
        DFS(i-1)
        count += 1

print(count)

 

연결 요소가 뭔지 몰라서 찾아보니 연결 그래프? 쉽게 말해 한 묶음으로 볼 수 있는 것들이 몇 개인지 세면 되는 것 같다. 깊이 우선 탐색으로 새로 시작하는 횟수를 세면 정답! 처음에 sys.setrecursionlimit(10000) 이거 안 써서 런타임 에러 났다. (정답)

 

---

 

024. 신기한 소수 (백준 2023번)

 

https://www.acmicpc.net/problem/2023

 

from sys import stdin
import sys

sys.setrecursionlimit(10000)

num = int(stdin.readline())
odd = [1, 3, 5, 7, 9]

def isPrime(n):
    for i in range(2, n//2 + 2):
        if n % i == 0:
            return False
    return True


def DFS(n):
    if len(str(n)) == num:
        print(n)
    else:
        for i in odd:
            if isPrime(10*n + i):
                DFS(10*n + i)

DFS(2)
DFS(3)
DFS(5)
DFS(7)

 

(정답)

 

---

 

025. ABCDE (백준 13023번)

 

https://www.acmicpc.net/problem/13023

 

from sys import stdin
import sys

sys.setrecursionlimit(10000)

n, m = map(int, stdin.readline().split())
data = [[] for i in range(n)]
visited = [False] * n

def DFS(v, depth):
    if depth == 5:
        print(1)
        exit()
    visited[v] = True
    for i in data[v]:
        if not visited[i-1]:
            DFS(i-1, depth+1)
    visited[v] = False # !

for i in range(m):
    a, b = map(int, stdin.readline().split())
    data[a-1].append(b)
    data[b-1].append(a)

for i in range(n):
    if not visited[i-1]:
        DFS(i-1, 1)

print(0)

 

주석으로 느낌표 써둔 저 줄을 꼭 써야 한다!! 이번에 깊이가 5가 되지는 못 했어도 후에 다른 방식으로 깊이 5를 달성할 수 있기 때문인 것 같다. 아마도... (정답)

 

---

05-2 너비 우선 탐색

 

026. DFS와 BFS (백준 1260번)

 

https://www.acmicpc.net/problem/1260

 

from sys import stdin
from collections import deque

n, m, s = map(int, stdin.readline().split())
data = [[] for i in range(n)]
visited = [False] * n

for i in range(m):
    a, b = map(int, stdin.readline().split())
    data[a-1].append(b)
    data[b-1].append(a)

for i in range(n):
    data[i].sort()

def DFS(v):
    visited[v] = True
    print(v+1, end=" ")
    for i in data[v]:
        if not visited[i-1]:
            DFS(i-1)

def BFS(v):
    que = deque()
    visited[v] = True
    que.append(v+1)
    while que:
        v = que.popleft()
        print(v, end=" ")
        for i in data[v-1]:
            if not visited[i-1]:
                visited[i-1] = True
                que.append(i)

DFS(s-1)

print()
visited = [False] * n

BFS(s-1)

 

(정답)

 

---

 

027. 미로 탐색 (백준 2178번)

 

https://www.acmicpc.net/problem/2178

 

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
maze = []
visited = [[False] * m for _ in range(n)]
count = 0
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]

for i in range(n):
    maze.append(list(map(int, stdin.readline().strip())))

que = deque()

que.append((0, 0))
visited[0][0] = True
while que:
    v = que.popleft()
    for k in range(4):
        x = v[0] + dir[k][0]
        y = v[1] + dir[k][1]
        if x >= 0 and y >= 0 and x < n and y < m:
            if maze[x][y] != 0 and not visited[x][y]:
                que.append((x, y))
                visited[x][y] = True
                maze[x][y] = maze[v[0]][v[1]] + 1

print(maze[n-1][m-1])

 

처음에는 갈 수 있는 길이라는 것을 의미했던 1들에 수를 더해가며 깊이를 표현하는 아이디어가 포인트였던 문제! (정답)

 

---

 

028. 트리의 지름 (백준 1167번)

 

https://www.acmicpc.net/problem/1167

 

from sys import stdin
from collections import deque

n = int(stdin.readline())
data = [[] for _ in range(n)]

for _ in range(n):
    input = list(map(int, stdin.readline().split()))
    i = 1
    while input[i] != -1:
        data[input[0]-1].append((input[i], input[i+1]))
        i += 2

def BFS(v):
    que = deque()
    visited[v-1] = True
    que.append(v)
    while que:
        v = que.popleft()
        for i in data[v-1]:
            if not visited[i[0]-1]:
                visited[i[0]-1] = True
                que.append(i[0])
                dst[i[0]-1] = dst[v-1] +  i[1]

dst = [0] * n
visited = [False] * n

BFS(2)

maxIndex = 0
for i in range(n):
    if dst[i] > dst[maxIndex]:
        maxIndex = i

dst = [0] * n
visited = [False] * n

BFS(maxIndex+1)
print(max(dst))

 

일단 책에 있는 내용을 읽고 풀긴 했지만 이해는 못 한... (정답)