파이썬 알고리즘 278번 | [백준 1325번] 효율적인 해킹 - dfs ,bfs

Yunny.Log ·2022년 11월 27일

Algorithm

목록 보기

283/318

278. 효율적인 해킹

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>



< visited 추가한 bfs >
```python
from collections import deque
import sys

n,m = map(int, sys.stdin.readline().split())
dict = {} # 관계 결과 담아줄 사전 (인접 노드)
q = deque() # dfs 돌려줄 스택 
res = [0 for _ in range(n+1)] # 결과 (각 경우 별로 몇 개 해킹가능한 지)

for k in range(1,n+1) :
    dict[k] = []

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

for i in range(1,n+1) :
    visited = [0 for _ in range(n+1)]
    q.append(i)
    visited[i] = 1
    while q : 
        res[i]+=1
        now = q.pop()
        # print(q, now)
        for j in range(len(dict[now])): 
            if(visited[dict[now][j]] == 0) : 
                visited[dict[now][j]] = 1
                q.append(dict[now][j])
                    
# print(res)
# [0, 4, 4, 3, 1, 1]
max_num = max(res)

for r in range(1,n+1) : 
    if res[r] == max_num : 
        print(r, end = " ")


##  < 내 틀렸던 풀이, 문제점>

(1) DFS 풀이
```python

import sys

# 5 4
# 3 1
# 3 2
# 4 3
# 5 3
# {1: [3], 2: [3], 3: [4, 5]}

n,m = map(int, sys.stdin.readline().split())

dict = {} # 관계 결과 담아줄 사전 (인접 노드)
stk = [] # dfs 돌려줄 스택 
res = [0 for _ in range(n+1)] # 결과 (각 경우 별로 몇 개 해킹가능한 지)

for k in range(1,n+1) :
    dict[k] = []

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

for i in range(1,n+1) :
    stk.append(i)
    while stk : 
        res[i]+=1
        now = stk.pop()
        if(dict[now]) : 
            for j in range(len(dict[now])) : 
                stk.append(dict[now][j])

# print(res)
# [0, 4, 4, 3, 1, 1]
max_num = max(res)

for r in range(1,n+1) : 
    if res[r] == max_num : 
        print(r, end = " ")

~~-내 경우에는 단방향으로만 저장해둬가지고 VISITED 배열을 만들 필요가 없었다.~~
- 원래 VISITED 배열을 만들어야하는 경우는, MAP[1][2] 는 TRUE 이런 식으로 표시해둘 때 1에서 2를 방문하는 것이 수행됐으면 2에서 1을 방문하는 것을 방지해야 무한루프를 피할 수 있기 때문에 VISITED 를 수행해주었어야 하는 것이다.
~~-그러나 나는 어차피 단방향적으로 기록해두어서 VISITED 안해줌~~
=> 단방향으로 기록했어도 a, b 로 주어질 때 1,2 랑 2,1 이 들어올 수 있기에 나의 생각은 터무니없었던 것

그런데 위와 같이 짜니깐 시간초과가 난다 ! 하핫

from collections import deque
import sys

# 5 4
# 3 1
# 3 2
# 4 3
# 5 3
# {1: [3], 2: [3], 3: [4, 5]}

n,m = map(int, sys.stdin.readline().split())

dict = {} # 관계 결과 담아줄 사전 (인접 노드)
q = deque() # dfs 돌려줄 스택 
res = [0 for _ in range(n+1)] # 결과 (각 경우 별로 몇 개 해킹가능한 지)

for k in range(1,n+1) :
    dict[k] = []

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

for i in range(1,n+1) :
    q.append(i)
    while q : 
        res[i]+=1
        now = q.pop()
        if(dict[now]) : 
            for j in range(len(dict[now])) : 
                q.append(dict[now][j])

# print(res)
# [0, 4, 4, 3, 1, 1]
max_num = max(res)

for r in range(1,n+1) : 
    if res[r] == max_num : 
        print(r, end = " ")