[백준] 20560번: 맛집 탐방

🔈 문제

은수는 맛집을 탐방하러 도시로 여행을 떠날 것이다. 은수가 갈 도시에는 총 $N$개의 맛집이 있다.

도시에는 맛집에서 맛집으로 이동할 수 있는 일방통행 길이 $M$개 있고, 각 길의 중간에는 기념품 상점이 있다. 어떤 길은 출발하는 맛집과 도착하는 맛집이 같을 수도 있으며, 여러 길이 같은 맛집을 연결할 수도 있다.
은수는 도시의 맛집에서 여행을 시작해서, 길을 이용해 맛집을 탐방하다 도시의 맛집에서 여행을 끝낼 것이다. 여행을 시작한 곳과 여행을 끝낸 곳이 같을 필요는 없다.

도시는 은수가 사는 마을에서 멀리 떨어져 있기 때문에, 은수는 한 번의 여행에서 최대한 많은 맛집과 상점을 들르려고 한다. 특히, 여행 중에 모든 맛집을 방문하거나 모든 기념품 상점을 방문한다면 다음 여행에서 할인 혜택을 받을 수 있기 때문에 은수는 이런 여행이 가능한지 알고 싶어 한다. 우리가 할 일은, 은수의 여행 계획을 돕는 것이다.

 

📝입력

첫 번째 줄에 맛집의 수 $N$과 길의 수 $M$이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 500\,000$)
두 번째 줄부터 $M$줄에 걸쳐 각 길의 정보가 주어진다. 각 줄에는 두 수 $u$, $v$가 공백으로 구분되어 주어지는데, 이는 맛집 $u$에서 맛집 $v$로 가는 길이라는 것을 의미한다. (1≤  $u$, $v$ ≤  $N$)

 

📑출력

총 3개의 줄을 출력한다.
첫 번째 줄에는 은수가 $N$개의 맛집을 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.
두 번째 줄에는 은수가 $M$개의 기념품 상점을 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.
세 번째 줄에는 은수가 $N$개의 맛집을 모두 방문하면서, $M$개의 기념품 상점도 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.

 

📚 문제 풀이

 

문제를 다시 정리하면 

유향 그래프가 주어지고, 한 점에서 시작하여 모든 노드를 방문할 수 있는 경우, 한 점에서 시작하여 모든 간선을 지나갈 수 있는 경우를 찾는 것이다. 

세번째에 구해야 하는 값은 앞서 말한 두 상황을 찾아 둘의 AND 관계로 알 수 있다. 

 

 

그래프를 한번 머리속으로 그려보자. 

모든 노드를 방문했는데, 방문하지 못하는 간선이 있을까?

있다.

아래와 같은 상황을 살펴보면 1 -> 2 -> 3 순으로 방문하면 모든 노드를 방문할 수는 있지만 1->3을 잇는 간선은 지나가지 못한다. 

1 -> 2 -> 3

 

그러면 반대로 모든 간선을 지나갔는데, 방문하지 못하는 노드가 있을까?

 

처음에는 없다고 생각하였다. 

모든 간선을 지나갔다는 것은 그 간선이 잇고 있는 두 노드를 지나갔다는 것이고, 그렇게하면 그래프에 있는 모든 노드를 방문했을거라고 생각했다.

 

하지만!!

놓친 점이 있었다.

 

그래프가 모두 연결되어 있지 않을 수도 있다는 점이다. 

 

즉 아래와 같은 형태의 그래프가 입력으로 주어질 수 있다. 

 

이렇게 된다면 1이나 2에서 시작하면 모든 간선은 지나갈 수 있지만, 모든 노드를 방문하는 것은 불가능하다!

 

이 점을 생각하였다면 이제 코드짜면 된다!

 

풀이는 우선 SCC를 만들고 DAG 그래프를 새로 그려주었다. 그리고 여기서 위상정렬을 수행하면서 위상정렬 경로가 유일한지 아닌지, 위상정렬 시작점이 유일한지 아닌지 등을 파악해주었다.

 

💻 코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
def dfs(cur:int):
    global idx, num
 
    idx += 1
    d[cur] = idx
    visited[cur] = True
    stk.append(cur)
 
    parent = d[cur]
 
    for nxt in graph[cur]:
        if d[nxt] == -1:
            parent = min(parent, dfs(nxt))
        elif visited[nxt]:
            parent = min(parent, d[nxt])
    
    if d[cur] == parent:
        cnt = 0
        while True:
            node = stk.pop()
            visited[node] = False
            scc_idx[node] = num
            cnt += edges_cnt[node]
            if cur == node: break
 
        scc_node[num] = cnt
        num += 1
 
    return parent
 
def topology(dag:list[list[int]], edges:list[int]) -> list[int]:
    global first, second
    queue = deque()
    level = [0]*num
    not_one = 0
 
    for i in range(num):
        if edges[i] == 0:
            queue.append((i,0))
            if len(dag[i]) + scc_node[i] >= 1:
                not_one += 1
                if not_one > 1:
                    second = False
 
    if len(queue) != 1:
        first = False
 
    while queue:
        cur,dep = queue.popleft()
        
        if level[dep]:
            first = False
        level[dep] += 1
 
        if len(dag[cur]) > 1:
            second = False
 
        if not first and not second:
            return
 
        for nxt in dag[cur]:
            edges[nxt] -= 1
 
            if not edges[nxt]:
                queue.append((nxt, dep+1))
 
    return
 
 
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
edges_cnt = [0]*(n+1)
for _ in range(m):
    u,v = map(int,input().split())
    edges_cnt[u] += 1
    graph[u].append(v)
 
d = [-1]*(n+1)
visited = [False]*(n+1)
stk = []
idx = 0
num = 0
scc_idx = dict()
scc_node = dict()
 
for cur in range(1, n+1):
    if d[cur] == -1:
        dfs(cur)
 
dag = [[] for _ in range(num)]
edges = [0]*num
 
for cur in range(1, n+1):
    for nxt in graph[cur]:
        if scc_idx[cur] != scc_idx[nxt]:
            dag[scc_idx[cur]].append(scc_idx[nxt])
            edges[scc_idx[nxt]] += 1
 
 
first = True
second = True
 
for i in range(num):
    if len(dag[i]) != len(set(dag[i])):
        second = False
        break
topology(dag, edges)
 
print(+first, +second, +first&second, sep='\n')

 

🍭 시행착오

 

열심히 치고박고 하였다.

 

중간에 런타임 에러(Error)는 동떨어져있는 그래프가 입력으로 주어지는 지 확인하기 위함이였다.

 

 

🔗 문제링크 

맛집 탐방

20560번: 맛집 탐방