EDOC 2023-W 1회차 과제 (그래프의 표현)

08-1. 그래프의 표현

 

046. 특정 거리의 도시 찾기 (백준 18352번)

 

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

 

from sys import stdin
from collections import deque

n, m, k, x = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
visited = [-1] * (n+1)
ans = []

def bfs(v):
    que = deque()
    que.append(v)
    visited[v] += 1
    while que:
        new = que.popleft()
        for x in g[new]:
            if visited[x] == -1:
                que.append(x)
                visited[x] = visited[new] + 1

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)

bfs(x)

for i in range(1, n+1):
    if visited[i] == k:
        ans.append(i)

if ans:
    ans.sort()
    for x in ans:
        print(x)
else:
    print(-1)

책을 많이 참고하며 푼 풀이 (정답)

 

from sys import stdin
from collections import deque

n, m, k, x = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
visited = [-1] * (n+1)
ans = []

def bfs(v):
    que = deque()
    que.append(v)
    visited[v] += 1
    while que:
        new = que.popleft()
        if visited[new] >= k: # 이 if문만 추가
            break
        for x in g[new]:
            if visited[x] == -1:
                que.append(x)
                visited[x] = visited[new] + 1

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)

bfs(x)

for i in range(1, n+1):
    if visited[i] == k:
        ans.append(i)

if ans:
    ans.sort()
    for x in ans:
        print(x)
else:
    print(-1)

생각해보니 최단 거리가 k인 노드까지 탐색이 끝났으면 더 탐색을 안 해도 되는거 아닌가? 라는 생각이 들어 살짝 수정한 코드. (정답) 시간이 1928ms에서 1588ms로 살짝 단축되었다. 

 

---

 

047. 효율적인 해킹 (백준 1325번)

 

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

 

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
reliable = [0] * (n+1)

def bfs(v):
    que = deque()
    que.append(v)
    visited[v] = True
    while que:
        new = que.popleft()
        for x in g[new]:
            if not visited[x]:
                que.append(x)
                visited[x] = True
                reliable[x] += 1

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[a].append(b)

for i in range(1, n+1):
    visited = [False] * (n+1)
    bfs(i)

max = max(reliable)
for i in range(1, n+1):
    if reliable[i] == max:
        print(i, end=" ")

이게 교재랑 유사한 코드인데... 왜인지 모르게 시간 초과가 났다. PyPy로 제출해도 똑같이 시간 초과. (오답) 뭐지 책에는 통과한 코드만 기재하는 거 아닌가? 아무튼 질문게시판이랑 구글을 뒤졌다. 

 

from sys import stdin
from collections import deque

n, m = map(int, stdin.readline().split())
g = [[] for _ in range(n+1)]
hacking = [0] * (n+1)

def bfs(v):
    cnt = 0
    que = deque()
    visited = [False] * (n+1)
    que.append(v)
    visited[v] = True
    while que:
        new = que.popleft()
        for x in g[new]:
            if not visited[x]:
                que.append(x)
                visited[x] = True
                cnt += 1
    return cnt

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    g[b].append(a)

for i in range(1, n+1):
    hacking[i] = bfs(i)

max = max(hacking)
for i in range(1, n+1):
    if hacking[i] == max:
        print(i, end=" ")

서치해본 결과 파이썬 또는 PyPy로 시간 초과를 해결할 수 있는 방법은 여러가지가 있지만, 나머지 방법은 너무 어렵거나 코드를 많이 수정해야 해서 그나마 책의 풀이와 비슷한 해결법을 찾았다. 책에서는 신뢰하는 것을 기준으로 그래프에 저장하고 매번 신뢰도 리스트를 업데이트한다. 그런데 반대로 해킹할 수 있는 것을 기준으로 그래프에 저장하면 한 번 탐색할 때 바로 그 컴퓨터를 해킹했을 때 해킹할 수 있는 컴퓨터의 개수를 구할 수 있게 된다. 사실 이게 시간에 얼마나 큰 영향을 미치는지는 모르겠으나, 이 방법으로 제출하니 파이썬은 여전히 시간 초과이지만 PyPy로는 정답 처리가 되었다. 이전 코드와 다른 점은 그래프 저장을 g[b].append(a)로 바꾼 것과 신뢰도를 저장하는 배열에서 해킹 가능한 컴퓨터 수를 저장하는 배열로 바뀐 것(두 개의 결과는 같지만 과정이 다르다.) 두가지뿐이다. (정답)

[참고] https://velog.io/@hyuntall/%EB%B0%B1%EC%A4%80-1263%EB%B2%88-%EC%8B%9C%EA%B0%84-%EA%B4%80%EB%A6%AC-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

---

 

048. 이분 그래프 (백준 1707번)

 

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

 

from sys import stdin
import sys

sys.setrecursionlimit(10**6)

def dfs(v):
    check = True
    visited[v] = True
    for x in g[v]:
        if not visited[x]:
            set[x] = (set[v] + 1) % 2
            dfs(x)
        else:
            if set[x] == set[v]:
                check = False
                break
    return check

k = int(stdin.readline())
for _ in range(k):
    v, e = map(int, stdin.readline().split())
    g = [[] for _ in range(v+1)]
    visited = [False] * (v+1)
    set = [0] * (v+1)

    for _ in range(e):
        a, b = map(int, stdin.readline().split())
        g[a].append(b)
        g[b].append(a)

    isBip = True
    for i in range(v+1):
        if not dfs(i):
            isBip = False
            break
    
    if isBip:
        print("YES")
    else:
        print("NO")

이 문제의 핵심 원리는 다음과 같다. "모든 노드에 대해 각각 DFS 탐색 알고리즘을 적용해 탐색을 수행한다. DFS를 실행할 때 현재 노드와 연결된 노드 중 이미 방문한 노드가 나와 같은 집합니면 이분 그래프가 아닌 것으로 판별한다. 실행 결과가 이분 그래프가 아니면 이루 노드는 탐색하지 않는다." 이분 그래프인지 판별하려면 왜 이러한 알고리즘을 적용해야 하는지는 아직 명확히 이해는 안 되지만 서치해서 그림들을 보니까 대충 느낌은 알 것 같다. 아무튼 이 원리만 알면 코드 짜는 건 어렵지 않았다. 아 그리고 RecursionError가 나지 않으려면 sys.setrecursionlimit(10**6)를 적어주어야 한다. (정답)

 

---

 

049. 물통 (백준 2251번)

 

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

 

from sys import stdin
from collections import deque
import copy

sender = [0, 0, 1, 1, 2, 2] # 0:A, 1:B, 2:C
receiver = [1, 2, 0, 2, 0, 1]
visited = [[False for _ in range(201)] for _ in range(201)]
ans = [False] * (201)

def bfs(cap):
    que = deque()
    que.append([0, 0, cap[2]])
    visited[0][0] = True
    ans[cap[2]] = True
    while que:
        cur = que.popleft()
        for i in range(6):
            nxt = copy.deepcopy(cur)
            if nxt[sender[i]] != 0:
                dif = min(nxt[sender[i]], cap[receiver[i]] - nxt[receiver[i]])
                nxt[receiver[i]] += dif
                nxt[sender[i]] -= dif
            if not visited[nxt[0]][nxt[1]]:
                que.append(nxt)
                visited[nxt[0]][nxt[1]] = True
                if nxt[0] == 0:
                    ans[nxt[2]] = True

capacity = list(map(int, stdin.readline().split()))
bfs(capacity)

for i in range(201):
    if ans[i]:
        print(i, end=" ")

이 문제를 보고 어떻게 그래프를 떠올리는 거지..?? 아무튼 이런 경우의 수?를 가지쳐가면서 체크해야 하는 경우에 그래프 탐색이 이용될 수 있다는 것을 알게 되었다. 그리고 변화량을 먼저 새로운 변수에 저장해두고 receiver에는 변화량 더하고 sender에는 변화량 빼는 게 편하다는 점과 현재 노드(cur)와 다음 노드(nxt)를 따로 두는 게 편하다는 점이 인상 깊었다.

추가로!! nxt = cur 이렇게 하면 얕은 복사가 일어난다. 얕은 복사는 하나의 객체를 가리키는 주소만 복사가 되는 것이므로 하나가 변하면 다른 하나도 변하게 된다. 하지만 여기서는 원래 객체가 갖는 값들과 똑같은 값들을 갖는 완전히 새로운 객체를 만드는 깊은 복사가 필요하기 때문에 nxt = copy.deepcopy(cur) 라고 써야 한다. (정답)

 

---

 

추가적인 의문

DFS로 풀 수 있는 문제는 모두 BFS로도 풀 수 있고 반대도 그러한가? 아니면 둘 중 하나로만 풀 수 있는 문제도 있는 걸까?