240212 [BOJ/백준] 2606. 바이러스 (+수정)

 

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

2606번: 바이러스

---

나의 코드

def virus_num(num):
    visited = [0]*(V+1)  #스택 만들기
    stack = []
    visited[num] = 1
    while True:
        for w in adjl[num]:
            if visited[w] == 0:
                stack.append(num)
                num = w
                visited[num] = 1
                break
        else:
            if stack:
                num = stack.pop()
            else:
                break
    return visited


V = int(input())
E = int(input())
adjl = [[] for _ in range(V+1)]
for _ in range(E):
    i, j = map(int, input().split())
    adjl[i].append(j)
    adjl[j].append(i)

# print(adjl)
print(virus_num(1).count(1)-1)

 

---

결과

 

---

두번째 코드 - 재귀함수 

def virus_num(i):
    
    infection[i] = 1
    for w in adjl[i]:
        if infection[w] == 1:
            continue
        else:
            infection[w] = 1
            i = w
            virus_num(i)
    return infection



V = int(input())
E = int(input())
infection = [0]*(V+1)
adjl = [[] for _ in range(V+1)]
for _ in range(E):
    i, j = map(int, input().split())
    adjl[i].append(j)
    adjl[j].append(i)

# print(adjl)
print(virus_num(1).count(1)-1)

 

결과

재귀함수로 풀면서 코드길이가 짧아졌다. 시간과 메모리는 같은 것 보면 같은 방식으로 돌아가는 것 같긴 하다.

---

학교에서 배운  dfs를 이용한 문제를 쉽게 풀 수 있었다. 알고리즘 한 문제를 푸는데 쓰는 시간이 너무 많은 것 같다는 의견에 30분을 타이머로 재고 풀었다. 그래도 dfs에 대해 잘 이해하고 풀어서인지 막힘없이 풀 수 있었고 6분 몇 초를 남긴 시간에 결과를 볼 수 있었다! 너무 기쁘다!! 재귀함수로도 풀 수 있다고 했고 그 방법을 들어봤으니 지금 다시 풀어보려고 한다.

+ 그건 실패...ㅜㅜ 여기까지 한 것으로 만족하고 내일 코드보여주면서 물어봐야겠다.

+ 정말 간단한 문제였는데 inpection리스트를 밖으로 빼서 맞힐 수 있었다.