[모각코] 210731 Today I Learned

<백준 17220번 - 마약수사대>

 

지난 주 초반에 풀다가 못 풀어서 포기한 문제인데 드디어 풀었다.

친구랑 같이 상의해 본 문제긴 한데 그래도 내 코드로 풀고 싶어서 계속 붙잡고 있다가.. ㅋㅋ 며칠 동안 계속 안 풀려서 그냥 친구 코드 참고했다.

 

내 기존 코드에서는 원산지 여부를 if문에 all() 함수를 사용해서 처리했다. 유향 그래프이므로 인접리스트에 해당 값이 요소로 들어가있지 않으면 원산지이기 때문. 근데 이 방식으로 했더니 원산지가 검거되어도 dfs는 계속 돌아가는 문제가 생겼다. 원산지가 검거되면 해당 원산지로부터 공급받는 곳을 dfs로 확인할 필요가 없다. 따라서 root 리스트를 만들어서 원산지 여부를 확인하고 원산지이고, 해당 노드를 방문하지 않은 경우에만 dfs를 돌려주었다. 이렇게 하면 두 원산지로부터 공급받는 노드가 있는 경우, 하나의 원산지가 검거되더라도 다른 원산지로 부터 공급받을 수 있으므로 그 경우에도 count += 1을 할 수 있다.

 

 

 #내 기존 코드에서 친구 코드 참고하여 수정한 코드

import sys
input = sys.stdin.readline
def dfs(v):
    global count
    visited[v] = 1
    for i in range(len(adjList[v])):
        w = adjList[v][i]
        if chr(v+65) in check:
            check.append(w)
            break
        if w not in check and not visited[ord(w)-65]:
            count += 1
            dfs(ord(w)-65)
        
n, m = map(int, input().split())
adjList = [[] for i in range(n)]
visited = [0 for i in range(n)]
root = [1 for i in range(n)]
count = 0

for j in range(m):
    a, b = input().split()
    adjList[ord(a)-65].append(b)
    root[ord(b)-65] = 0
check = list(input().split())

for i in range(m):
    if root[i] == 1 and chr(i+65) not in check:
        dfs(i)
print(count)

 

며칠 동안 풀면서 만든 다른 코드들은 여기에. (2021.07.20 - [Coding/백준] - [Python] 백준 17220번 - 마약수사대)