백준 algorithm study 1948 2667 1389 위상정렬 bfs python

파이썬 알고리즘 : 임계경로, 단지번호붙이기, 케빈 베이컨의 6단계 법칙

백준 1948, 백준 2667, 백준 1389

2023년 9월 2일 알고리즘 문제풀이

문제 1 백준 1948

문제 링크

1차 시도

나의 생각

위상정렬을 이용해 풀고자 하였다. 단 시작지점은 진입차수가 0인 것이 문제의 조건이므로 큐에 시작도시를 넣고 반복하였다. 결국 도착지에 갈때까지 비용을 계속 더해주고, 간선을 이용할 떄마다 카운트 해주었다.

예제를 입력했을 떄 결과값이 실제 정답보다 크게 나오기도 했고, 경로 탐색이 내가 예상한대로 되지 않았다. 아무래도 문제를 제대로 이해하지 못한채 그냥 위상정렬만 적용해서 해결하지 못하고 있는것 같다. 애초에 이 문제를 왜 위상정렬로 풀어야 하는지도 모르겠다.. 공부해봐야겠다.

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
level = [0 for _ in range(n+1)]
for _ in range(m):
    a,b,t = map(int,sys.stdin.readline().split())
    graph[a].append([b,t])
    level[b] += 1
start, arrive = map(int,sys.stdin.readline().split())

arr = deque()
arr.append(start)

cnt = 0
ans = 0
while arr:
    now = arr.popleft()
    cnt += 1
    if now == arrive:
        break
    for i in graph[now]:
        next = i[0]
        time = i[1]
        level[next] -= 1
        if not level[next]:
            arr.append(next)
            ans += time

print(cnt)
print(ans)

2차 시도

출처1

출처2

나의 생각

우선 왜 경로문제에서 위상정렬을 사용할까? 위상정렬을 사용해야겠다고 판단을 할 수 있는 근거가 무엇일지 고민해보았다.

이전 게시글에서 말했지만 위상정렬을 통해 변의 방향을 거스리지 않도록 나열할 수 있다. DAG(Directed Acyclic Graph, 방향성 비순환 그래프)란 이름 그대로 방향성이 있는 엣지로 구성되어있지만, 순환(cycle)이 없다. 이 DAG의 모든 노드들을 선형 순서로 나열하는 알고리즘이 위상정렬(Topological Sorting)이다.

현재 문제의 조건들을 살펴보자.

  • 모든 도로가 일방통행 : 간선의 방향성을 의미
  • 싸이클이 없다 : 비순환

따라서 문제의 ‘월드 나라’는 DAG라는 뜻이므로 위상정렬을 통해 경로를 나열해야겠다는 결론이 도달할 수 있다.

  • 경로문제네. 위상 정렬로 풀어볼까..? (X)
  • 도로가 일방통행이고 싸이클이 없네. DAG구나. 그럼 위상 정렬로 풀어볼까? (O)

무수히 많은 사람이 시작도시부터 도착도시까지 모든 경로를 탐색한다고 한다. 따라서 출발도시부터 도착도시까지 가는 경로 중 가장 오래걸리는 루트를 찾아야 한다. 이것이 가능한 이유는 싸이클이 없기 때문이다. 싸이클이 있다면 무한히 싸이클에서 순환하며 안들어올 수도 있으니까..

도착하는 시간은 상대적으로 간단하다. 위상정렬을 통해 각 간선에 걸리는 시간을 누적으로 더해주면서 업데이트하면 된다. 아래 코드에서 cnt가 출발도시 start에서 각 도시까지 걸리는 시간을 표시하는 배열이다. 기존 배열에 이미 값이 존재한다면 비교하여 더 큰 값으로 업데이트해주면 된다. 최소비용을 찾던 다익스트라의 반대 라고 생각하면 좋을려나..

하지만 문제에서 그 최댓값을 찾은 후 지나온 경로(간선)의 갯수도 요구한다. 기존 위상정렬의 로직은 유지하되, back_graph라는 배열을 새로 만들었다. 이 배열의 역할은 해당 지점까지 지나온 도시들을 표시하기 위한 것이다. 새롭게 계산한 경우가 기존에 저장한 값보다 더 큰 비용일 경우, 새롭게 time을 업데이트하면서 기존에 저장하고 있던 지나간 도시들 리스도 now 1개로 초기화 해준다. 기존과 새로운 경우가 같은 값을 가질때는? 모두 확인해봐야 하므로 바꾸는 것이 아니라 append로 추가해준다.

이 후 과정은 도착지부터 다시 역으로 BFS를 통해 탐색하는 과정이다. 단 한번 지난적 있는 경로는 피하기 위해 route라는 set 자료구조를 통해 중복을 방지하고 있다.

결과

이해

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for _ in range(n+1)]
back_graph = [[] for _ in range(n+1)]
arr = deque()
level = [0 for _ in range(n+1)]
time = [0 for _ in range(n+1)]

for _ in range(m):
    a, b, t = map(int, sys.stdin.readline().split())
    graph[a].append([b, t])
    level[b] += 1

start, arrive = map(int, sys.stdin.readline().split())
arr.append(start)

while arr:
    now = arr.popleft()
    for next in graph[now]:
        next_place = next[0]
        next_time = next[1]
        level[next_place] -= 1
        if time[next_place] < time[now] + next_time:
            time[next_place] = time[now] + next_time
            back_graph[next_place] = [now]
        elif time[next_place] == time[now] + next_time:
            back_graph[next_place].append(now)

        if not level[next_place]:
            arr.append(next_place)

arr = deque()
arr.append(arrive)
route = set()
while arr:
    now = arr.popleft()
    for x in back_graph[now]:
        if (now, x) not in route:
            route.add((now, x))
            arr.append(x)

print(time[arrive])
print(len(route))

문제 2 백준 2667

문제 링크

1차 시도

나의 생각

지도에서 집을 한개 발견하면 BFS를 통해 연결된 모든 집을 0으로 처리하며 카운트하여 다시 중복하여 세는 것을 방지해주었다. 더이상 근접한 집이 없다면 갯수를 정답 배열에 추가하였다. 모든 좌표를 탐색한 결과로 나타나는 정답 배열의 길이가 단지의 수를 나타낸다. 정렬을 통해 문제에 알맞게 출력하였다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import sys
from collections import deque

n = int(sys.stdin.readline())

tmp = []
board = [[0 for _ in range(n+1)] for _ in range(n+1)]
ans = []
for _ in range(n):
    tmp.append(list(sys.stdin.readline().rstrip()))

for i in range(n):
    for j in range(n):
        if tmp[i][j] == '1':
            board[i+1][j+1] = 1
        else:
            board[i+1][j+1] = 0


def find(board):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if board[i][j]:
                arr = deque()
                arr.append([i, j])
                board[i][j] = 0
                ans.append(check(arr, 0))


def check(l, num):
    da = [0, -1, 0, 1]
    db = [1, 0, -1, 0]
    while l:
        p, q = l.popleft()
        num += 1
        for i in range(4):
            np = p + da[i]
            nq = q + db[i]
            if np < 1 or np > n or nq < 1 or nq > n:
                continue
            if board[np][nq]:
                l.append([np, nq])
                board[np][nq] = 0
    return num


find(board)
ans.sort()
print(len(ans))
print(*ans, sep='\n')

문제 3 백준 1389

문제 링크

1차 시도

나의 생각

BFS를 통해 두 사람간의 케빈 베이컨 수를 반환하도록 함수 search를 정의하였다. 이를 통해 한 사람과 다른 사람들과의 케빈 베이컨 수의 총 합을 구하는 함수 cal을 정의하였다. 모든 사람에게 이 함수를 적용하고 최솟값을 도출하였다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def cal(s):
    arr = [0 for _ in range(n+1)]
    for i in range(1,n+1):
        arr[i] = search(s,i)
    return sum(arr)


def search(a,b):
    visited = [False for _ in range(n+1)]
    q = deque()
    q.append([a,0])
    visited[a] = True
    while q:
        now,cnt = q.popleft()
        if now == b:
            return cnt
        for next in graph[now]:
            if not visited[next]:
                visited[next] = True
                q.append([next,cnt+1])

min_val = 1e9
ans = [0]
for i in range(1,n+1):
    tmp = cal(i)
    if tmp < min_val:
        min_val = tmp
        ans[0] = i
    elif tmp == min_val:
        ans.append(i)
print(min(ans))

2차 시도

나의 생각

내가 푼 문제이지만 반례를 발견해버렸다. 두번쨰로 낮은 케빈 베이컨 수를 가진 사람이 2명 이상이고 그 사람들 이후 가장 낮은 케빈 베이컨 수를 가진 사람이 나타난다면 내 코드는 잘못된 값을 도출한다. 예시로 설명해보겠다.

예시

6 8 1 2 2 3 3 4 4 5 5 6 6 1 6 2 6 3

사람번호 1 2 3 4 5 6 케빈 베이컨 수
1 0 1 2 3 2 1 9
2 1 0 1 2 2 1 7
3 2 1 0 1 2 1 7
4 3 2 1 0 1 2 9
5 2 2 2 1 0 1 8
6 1 1 1 2 1 0 6

정답은 6이어야 하지만 출력은 3이 된다.

이를 해결하기 위해 모든 케빈베이컨 수를 구해서 알맞은 index로 하여 배열에 저장한 후 최솟값을 찾았다. 이 후 1부터 확인하며 최솟값인 index를 찾으면 출력하여 가장 낮은 index가 나오도록 하였다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def cal(s):
    arr = [0 for _ in range(n+1)]
    for i in range(1,n+1):
        arr[i] = search(s,i)
    return sum(arr)


def search(a,b):
    visited = [False for _ in range(n+1)]
    q = deque()
    q.append([a,0])
    visited[a] = True
    while q:
        now,cnt = q.popleft()
        if now == b:
            return cnt
        for next in graph[now]:
            if not visited[next]:
                visited[next] = True
                q.append([next,cnt+1])


ans = [1e9 for _ in range(n+1)]
for i in range(1,n+1):
    ans[i]= cal(i)
tmp = min(ans)
for i in range(1,n+1):
    if ans[i] == tmp:
        print(i)
        break
CATALOG
    algorithm