(알고리즘)SWEA 1348 파이썬 Python

문제

SWEA 1348 공통조상 : https://swexpertacademy.com/main/code/problem/problemDetail.do

풀이방법

해당 문제의 핵심은 두개의 정점에서 공통의 부모를 찾는 방법이다. 나는 그냥 간단하게 첫번째 인자에서 받은 노드부터 루트까지 찾으면서 방문한 경우 방문을 체크하고 두번째 노드부터 다시 부모를 탐색하며 처음으로 방분한 곳을 만나게 될 시 해당 노드가 공통 부모로 저장하는 방식을 택했다.
그 이후 공통부모에서 다시 자식을 찾는 방법으로 진행했다.
bfs를 3번 진행하였다.

코드

from collections import deque
T=int(input())

for test in range(1,T+1):
    ans=0
    a,b,c,d=map(int, input().rstrip().split(' '))
    m1=[[]for _ in range(a+1)]
    m2=[[]for _ in range(a+1)]
    get=list(int(x) for x in input().rstrip().split(' '))
    for i in range(len(get)//2):
        m1[get[i*2]].append(get[i*2+1])
        m2[get[i*2+1]].append(get[i*2])
    #두개의 트리를 만들었다. 하나는 노드에서 부모를 찾을 수 있게, 하나는 루트에서 자식 노드를 찾을 수 있게
    visit=[0 for _ in range(a+1)]
    visit[c]=1
    q=deque()
    q.append(c)
    while(len(q)!=0):
        now=q.popleft()
        for i in m2[now]:
            if(visit[i]==0):
                q.append(i)
                visit[i]=1
                #첫번재 인자에서 루트까지 노드를 찾는다
    q.append(d)
    visit[d]=1
    common=-1
    while(len(q)!=0):
        now=q.popleft()
        check=False
        for i in m2[now]:
            if(visit[i]==0):
                q.append(i)
                visit[i]=1
            else:
                common=i
                check=True
        if(check): #방문한 적이 있는 노드의 경우 해당 노드가 공통부모
            break
    visit=[0 for _ in range(a+1)]
    q.clear()
    q.append(common)#부모노드부터 자식을 찾는다
    visit[common]=1
    ans+=1
    while(len(q)!=0):
        now=q.popleft()
        for i in m1[now]:
            if(visit[i]==0):
                q.append(i)
                visit[i]=1
                ans+=1
    print(f"#{test} {common} {ans}")

후기

SSAFY시작을 하다 보니 SWEA를 많이 풀게 될듯? 이제 슬슬 자바로 알고리즘문제를 푸는 습관을 들여야겠다. 근데 파이썬이 너무 편하긴 해;; 사기야;;;