[dfs,bfs/백준] 4803번 : 트리

- 문제 : https://www.acmicpc.net/problem/4803

 

Gold Level4 문제

주어진 정보로 트리를 만든다음, 트리의 갯수를 구하는 문제였다

트리를 찾는 건 어렵지 않았는데, 사이클을 이루는 그래프의 경우에는 트리가 되지 못하므로, 사이클이 되는 경우도 생각을 해야했다. 이 과정을 나름대로 구현해봤지만 잘되지 않아서 풀이를 보고 풀었다 

 

사이클이 되려면

1.

처음에는 방문한 노드를 다시 지나가는 경우에 사이클이 생성된다고 생각했다. 하지만 확인해보니 탐색 시 상,하,좌,우로 움직이므로 그러다가 방문한 노드를 다시 들릴 수 있다는 것을 알았다. 

2.

그래서 시작한 노드를 다시 지나가는 경우를 생각해서 result =[]를 추가한 뒤, result에 방문한 노드의 좌표들을 추가하다가

처음 노드를 다시 지나가면 사이클이 된다고 생각했다. 

하지만 이 경우는 다음이 반례다. 시작한 노드에서 시작했을 때 사이클이 생성되기는 하지만, 시작 노드가 사이클에 포함되지 않는다. 

(B

  BBBB

  BBBB)

 

혼자서 엄청 삽질하다가 결국 답지를 보고 풀었다

 

 

- 정답 풀이 1:

2번 풀이보다 이게 더 이해가 잘가서 적었다. 

이전에 풀었던 bfs와 다른 점이 원래 방문하지 않은 노드라면 방문 처리를 하고, queue.append()를 진행하는데 

여기서는 방문 처리를 시작할 때 하는지 모르겠다 

 

참고한 블로그

import sys
from collections import deque
input = sys.stdin.readline

def bfs(v):
    isTree = True
    queue=deque()
    queue.append(v)
    while queue:
        x = queue.popleft()
        #여기
        if visit[x] == 1:
            isTree = False
        visit[x] = 1
        for i in data[x]:
            if not visit[i]:
                queue.append(i)
    return isTree

case = 0
while True:
    n,m = map(int,input().split())
    if n == 0 and m == 0 :
        break
    case += 1
    data = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        data[a].append(b)
        data[b].append(a)
    visit = [0] * (n + 1)
    count = 0
    
    for i in range(1,n+1):
        if visit[i] == 1:
            continue
        if bfs(i) :
            count += 1
    
    if count == 0 :
        print("Case {}: No trees.".format(case))
    elif count == 1:
        print("Case {}: There is one tree.".format(case))
    else:
        print("Case {}: A forest of {} trees.".format(case,count))

 

- 정답 풀이 2:

 

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

def dfs(prev,v):
    visit[v] = 1
    for i in data[v]:
        if i == prev:
            continue
        if visit[i]:
            return False
        if not dfs(v,i):
            return False
    return True

num = 0           
while True:
    n,m = map(int,input().split())   
    if n == 0 and m == 0 :
        break 
    num += 1
    data = [[] for _ in range(n+1)]
    visit = [0] * (n+1)
    for _ in range(m):
        a,b = map(int,input().split())
        data[a].append(b)
        data[b].append(a)
        
    count = 0
    for i in range(1,n+1):
        if not visit[i]:
            if dfs(0,i):
                count += 1
            
    if count == 0 :
        print("Case " + str(num) + ": No trees.")
    elif count == 1:
        print("Case " + str(num) + ": There is one tree.")
    else:
        print("Case " + str(num) + ": A forest of " + str(count) + " trees.")

 

- 시도해본 풀이 :

계속 16%에서 틀렸다;

 

import sys
input = sys.stdin.readline

def dfs(v):
    visit[v] = 1
    global flag
    for i in data[v]:
        if visit[i]:
            flag = False
        else :
            dfs(i)
num = 1            
while True:
    n,m = map(int,input().split())   
    if n == 0 and m == 0 :
        break 
    num += 1
    data = [[] for _ in range(n+1)]
    visit = [0] * (n+1)
    for _ in range(m):
        a,b = map(int,input().split())
        data[a].append(b)
        
    count = 0
    for i in range(1,n+1):
        if not visit[i]:
            flag = True
            dfs(i)
            if flag:
                count += 1
            
    if count == 0 :
        print("Case " + str(num) + ": No trees.")
    elif count == 1:
        print("Case " + str(num) + ": There is one tree.")
    else:
        print("Case " + str(num) + ": A forest of " + str(count) + " trees.")