0907 Algorithm - 2606 virus

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

초기 구상과정

처음 문제를 풀 때 DFS 알고리즘을 사용하자고 생각했고 이 때 재귀호출을 쓸 것인지 while문을 이용할 것인지 고민했다. 공부를 했음에도 머리 속에 재귀호출의 방법을 떠오르지 않고 while 방법이 먼저 떠올라서 while로 구현했지만 제출하고 나서 fail... 다시 수정했지만 제자리걸음이라 재귀호출 방식을 다시 찾아보고 공부해서 소스코드로 삼아 다시 재귀함수형태로 구현하여 pass를 했다.

코드 - ver. correct

import sys
sys.stdin = open('virus.txt', 'r')

N = int(sys.stdin.readline())
arr = [[] for _ in range(N + 1)]
for i in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

visit = [0] * (N + 1)
cnt = -1
def go_step(n):
    visit[n] = 1
    global cnt
    cnt += 1
    for candidate in arr[n]:
        if not visit[candidate]:
            go_step(candidate)

go_step(1)
print(cnt)

코드 - ver. fail

import sys
sys.stdin = open('virus.txt', 'r')

N = int(sys.stdin.readline())
arr = [[] for _ in range(N + 1)]
for i in range(int(sys.stdin.readline())):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)
S = [1]
visit = [0] * (N + 1)
visit[1] = 1
start = 1
while S:
    for nod in arr[start]:
        if not visit[nod]:
            visit[nod] = 1
            S.append(nod)
            start = nod
            break
    else:
        start = S.pop()  
result = sum(visit) - 1
print(result)

앞으로...

솔직히 말하자면 아직까지 문제점을 찾지 못했다. '왜 while에서는 오답이 뜰까?'에 대해서 더 공부해 봐야겠다.