목차
오랜만에 백준 DFS/BFS 문제를 다시 풀어보기로 하였다.
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
당연히 너무 직관적이고 바로 맞출 줄 알았는데, (DFS는 그러하였다.)
BFS로 풀어보려 하니 자꾸 틀렸다고 하고...... ㅠㅠ 창피하다.
내가 왜 틀렸는지 정리해보겠다.
아래는 오답 코드 :
# =================
# 틀린 코드 (run time error type error)
# =================
import sys
from collections import deque
def bfs(n):
connected = graph[n]
Q = deque([connected])
while Q:
connected = Q.popleft()
for each in connected:
if visited[each] == 0:
visited[each] = 1
Q.append(each)
input = sys.stdin.readline
n = int(input())
v = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(v):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n + 1)
visited[1] = 1
bfs()
print(sum(visited) - 1)
바보같이 노트북에서는 에러가 나지 않는다고, 의아해하면서 자꾸 제출해서 틀린 횟수만 증가시켰다.
알고보니 직전에 같은 문제를 DFS로 맞추어 성공했었고, 파이참이 DFS로 푼 코드를 실행시키면서 에러를 띄우지 않았던것. 파이참을 BFS 버전 코드로 재 실행하니, 노트북에서도 에러를 띄우고 에러 시점을 알려주어서 원인을 알게 되었다.
런타임에서 틀린 이유:
맨 처음 connected = graph[node] 후 connected를 Q에 넣는 코드는 일단 옳다.
node 자체가 아니라 node에 연결된 아이들을 봐야하기 때문에 connected = graph[node]로 보아야 하는 것이다.
여기서 첫 번째 실수가 있다. connected는 리스트이다.
리스트를 Q에 넣기 때문에,
Q = deque(); Q.append(connected); 라고 하거나
Q = deque(connected); 라고 했어야 했다.
하지만, 내가 실수 했던 것 처럼 Q = deque([connected])라고 하면 이중 리스트가 된다.
그래서 추후 Q.popleft를 했을 때 리스트가 빠져나오는 것이 아니라, 이중리스트가 나와서 포문을 돌릴 때 문제가 발생하였던 것. for each in connected: 를 하였을 때, each가 int가 아니라 여전히 리스트였고, visited[each]를 할 때 타입 에러발생!
list indices must be integers or slices, not list
하지만 비단 이것 뿐만이 문제가 아니었다.
while Q:
connected = Q.popleft()
for each in connected:여기서 connected는 리스트가 아니라 정수이다. 하나씩 연결 노드를 뽑아내는 것이기 때문이다.
그래서 for each in connected 가 아니라 for each in graph[connected]라고 불러야 한다. 안그럼
아래 에러가 발생한다.
TypeError: 'int' object is not iterable
그런데 타입 에러를 고치고나서도 이젠 틀렸습니다가 발생 ㅠㅠㅠ (아 창피.. 이런 문제를 이렇게 많이 오답을 내다니..)
이제 더 이상 런타임 에러는 발생하지지 않았지만, 채점 중에서 틀렸다고 발생했다.
문제 예제는 잘 맞았는데???
질문 게시판에서 여러 반례를 검색해보았고, 아래에서 잘못된 답을 얻음을 알 수 있었다.
인풋:
2
1
2 1
정답: 1
오답(나의답): 0
# =================
# 틀린 코드
# =================
import sys
from collections import deque
def bfs():
connected = graph[1]
Q = deque(connected)
while Q:
node = Q.popleft()
for each in graph[node]:
if visited[each] == 0:
visited[each] = 1
Q.append(each)
input = sys.stdin.readline
n = int(input())
v = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(v):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n + 1)
visited[1] = 1
bfs()
print(sum(visited) - 1)
이것은 내가 visited[n] = 1라고 방문기록을 한 시점을 잘못했기 때문이다.
.1) 큐에 넣기 전 방문여부를 확인하고, 방문 안한 것만 방문기록을 하고 넣는다.
.2) 일단 무조건 큐에 넣고, 큐에서 뽑을 때 방문 여부를 확인한다. 방문을 했다면 패스하고, 방문을 안했다면 방문 기록후 추가 탐색을 한다.
1) 또는 2)를 consistent 하게 진행해야 하는데, Q에 넣고 빼기전 이중으로 검사를 하면 시간복잡도가 올라가고, 반대로 검사를 놓치면 순회를 잘못한것이기다.
내가 잘못한 부분은 아래와 같다.
일단 글로벌 영역에서, bfs()을 부르기전에 visited[1] = 1이라고 기록했다면 큐에 넣기전에, 방문여부를 확인 + 방문기록을 했다는 뜻이다. 일단 1번 컴퓨터는 방문하지 않았다는 것이 보증되니까 말이다.
하지만 1에서 연결된 컴퓨터들은 아묻따 Q생성시에 바로 넣어주어버렸다.
.... Q생성할 때 묻지않고 넣어줄거면, Q에서 뽑아낼 때 확인을 하는 것이 맞다!
그래서 아래 처럼 해야만 한다.
def bfs():
connected = graph[1]
Q = deque(connected)
while Q:
node = Q.popleft()
visited[node] = 1
for each in graph[node]:
if visited[each] == 0:
Q.append(each)
참고 :
게시판에서 찾은 반례 모음:
글 읽기 - 2606번 바이러스 반례 모음
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
Recall DFS and BFS
Depth First Search (aka DFS, 깊이 우선 탐색)
DFS는 스택을 기반으로 만든다.
스택은 LIFO다. (Last In First Out)
그래서 먼저 들어온 것이 아니라 최근에 들어온 것 기반으로 처리한다.
그래프를 순회 하다가, 해야할 게 보이면 "어 이것도 있네? 여기도 방문!" 하는 식
Breadth First Search (aka BFS, 너비 우선 탐색)
BFS는 큐를 기반으로 만든다.
큐는 FIFO다. (First In First Out)
그래서 최근에 들어온 것이 아니라 먼저 요청 들어온 것 기반으로 처리한다.
그래프를 순회 하다가 해야할 게 보이면 "어 이것도 있네? 넌 나중에 보자. 난 해야할 게 이미 있어서~" 라고 하는 식
