[Python] 백준 17220번 - 마약수사대

문제 https://www.acmicpc.net/problem/17220

17220번: 마약수사대

 

dfs 골드3은 무리였나.. ㅋㅋㅋ

인접리스트 입력을 문자열로 받는 것부터가 어려워서 헤맸다. 아스키 코드 써서 간신히 해결.

2021.07.20 - [Python] - 아스키코드 변환 함수 ord(), chr()

 

유향그래프 문제도 거의 처음 푸는 것 같다.

 

check에 맨 마지막 줄에서 입력 받은 2 b c 를 리스트로 넣고 인덱싱 사용해서 문제를 풀었다.

check는 경찰이 소재를 파악하고 있기 때문에 check에 들어간 공급책으로부터 공급을 받는 다른 공급책들 또한 모두 마약 공급을 받을 수 없다. 따라서 check에 있는 공급책들과 연결된 공급책들은 check에 append해주었다.

check에 없는 경우 소재가 파악되지 않았기 때문에 계속 공급이 가능하므로 count += 1 을 해주었다.

 

그리고 마약 원산지는 케이스마다 다른데, 원산지는 다른 곳에서 공급받지 않으므로 인접리스트 내부에 존재하지 않는다. 이를 통해 원산지를 확인한 후 dfs 함수를 돌리기 위해 all을 사용하여 if문으로 조건을 주었다.

(all, any 정리할 것).

 

예제를 돌려봤는데 맞아서 제출해봤는데.. 역시나 틀렸다 !

테케를 모르면 난.. 방법을 생각해낼 수가 없는데..

이 문제는 혼자서는 더 이상 생각해내지 못할 것 같아서 스터디 한 후에 다시 풀어보려고 먼저 지금까지의 풀이를 기록한다.

 

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)
        if w not in check:
            count += 1
        if not visited[ord(w)-65]:
            dfs(ord(w)-65)
        
n, m = map(int, input().split())
adjList = [[] for i in range(n)]
visited = [0 for i in range(n)]
count = 0
for j in range(m):
    a, b = input().split()
    adjList[ord(a)-65].append(b)
check = list(input().split())
for i in range(m):
    if all(chr(i+65) not in j for j in adjList):
        dfs(i)
print(count)

 

 

 

 

 

---

 

 

 

 

#210731

와... 풀었다..ㅋㅋ....

아무리 해도 안 풀리길래 친구 코드 보고 참고했다. 원산지를 분류하고 원산지가 검거되면 아예 그 쪽 라인은 체크하지 않는 게 포인트였던 것 같다. 원산지 찾는 부분을 all함수 사용하여 if문으로 처리했었는데 root 리스트를 만들어서 처리하는 방식으로 바꿨다. 

조금 더 자세한 설명은 여기에 (2021.07.31 - [HUFS/HUFS 모각코 캠프] - [모각코] 210731 Today I Learned)

 

 

#친구 코드 기반으로 다시 푼 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(v):
    global count
    visited[v] = 1
    for i in adjList[v]:
        if not visited[ord(i)-65]:
            count += 1
            dfs(ord(i)-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)]
for j in range(m):
    a, b = input().split()
    adjList[ord(a)-65].append(b)
    root[ord(b)-65] = 0
    
check = list(input().split())
check = check[1:]
for i in check:
    visited[ord(i)-65] = 1

count = 0
for i in range(n):
    if root[i] == 1 and not visited[i]:
        dfs(i)
print(count)

 

 

 

#내 기존 코드를 친구 코드 참고하여 수정

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)

나름.. 10일 간의 사투...