[bfs/백준] 3584번 : 가장 가까운 공통 조상

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

 

스스로 푼 문제다! Gold Level4 문제 

처음에는 dfs에 각 노드에 해당하는 노드를 리스트에  넣어서 했더니 indexerror가 나서 일차 리스트로 바꾸고 bfs로 바꾸어서 진행했더니 정답이 떴다.

 

처음에는 어떻게 해야할지 고민이 되었는데, 시간초과와 메모리초과가 안 뜨려면 주어진 노드를 기준으로 진행해야겠다고 생각했다. 그러면 초기 데이터를 부모.append(자식)이 아니라 자식.append(부모)로해서 부모노드로 올라가는 방법으로 생각했다. 주어진 a,b에서 a를 기준으로 탐색을 진행해서 지나온 부모노드들을 방문처리한 후 b가 탐색할 때 방문처리 된 부모노드가 있다면 그게 문제 조건을 만족하는 노드이므로 그것을 반환하는 것으로 생각했다 

 

1.

dfs로 진행했을 때는 원하는 순간에 답을 return하지 못해서 그거때문에 조금 헤맸다

깊이탐색이 가장 적절하지만, 어차피 일차 리스트로 진행하는거라서 bfs로 바꾸고 break 조건을 상세히 해서 진행했더니 정답이 떴다 

 

2.

그리고 루트노드인 경우에도 처리하는게 헷갈렸다. 루트노드가 만약 답이라면 루트노드에는 부모 노드가 없으므로, 이에 대해서 따로 처리하는 로직이 있어야한다 

 

- 정답 풀이 :

from collections import deque

def bfs(v):
    queue = deque()
    queue.append(v)
    visit[v] = 1
    result = 0
    while queue:
        x = queue.popleft()
        parent = data[x]
        
        #루트노드가 정답인 경우
        if parent == 0 :
            visit[x] = 1
            result = x 
            break
        #루트노드가 정답이 아닌 경우
        if visit[parent]:
            result = parent
            break
        if not visit[parent]:
            visit[parent] = 1
            queue.append(parent)
    return result            
                           
for _ in range(int(input())):
    n = int(input())
    data = [0]*(n+1)    
    for _ in range(n-1):
        a,b = map(int,input().split())      
        data[b] = a
        
    x,y = map(int,input().split())
    visit = [0] * (n+1)
    bfs(x)
    result = bfs(y)
    
    print(result)

 

- 시도해본 풀이 :

 

import sys
sys.setrecursionlimit(10**6)

def dfs(v):
    parent = data[v]
    if not visit[parent]:
        if data[parent] != 0 :
            dfs(parent)
        visit[parent] = 1
    return parent             
                
for _ in range(int(input())):
    n = int(input())
    data = [0]*(n+1)    
    for _ in range(n-1):
        a,b = map(int,input().split())      
        data[b] = a
        
    answer = 0     
    x,y = map(int,input().split())
    visit = [0] * (n+1)
    visit[x] = 1
    dfs(x)
    visit[y] = 1
    answer = dfs(y)
    
    if data[answer] == 0 :
        print(answer)
    else:
        print(data[answer])