boj16947 서울 지하철 2호선

첨에 쉬울줄 알았는데 생각보다 오래 걸린 문제...

🎯우선 내 접근

1. 일단 순환역인지를 check할 수 있는 기록지 준비하기
2. 순환역이라면 바로 0을 넣어주고 아니라면 거리에 따라 1씩 증가시켜 return 해주기.

로직은 간단한데 구현하는 데에 시간이 좀 오래 걸렸다. while loop로 풀려고 끙끙대다보니 시간 오래 걸림.. 결국 재귀로 바꿈.. ㅋㅋㅋㅋㅋ

📍각 역이 순환역인지를 저장할 list를 하나 만들려고
모든 역에 대해서 DFS를 진행하면서 순환역인지를 확인했다.

방문한 노드에 대해 True를 처리해 주며
stack을 비웠음. 스택을 뺀 횟수가 2회 이상이고 인접노드에 스타트 노드가 들어있다면 순환구조라고 파악했다. 그래서 이를 while loop로 구현했는데... error가 났다.

이렇게 하면 문제가 뭘까 고민을 해보니까 일단 한 노드의 엣지가 3개 이상인 경우 문제가 되고, 하나의 엣지의 탐색을 끝낸 후에 다음 엣지를 탐색하게 될 때 무조건 start 노드를 채크하게 된다는 것이다. 그리고 cnt는 이미 하나의 edge를 탐색할 때 증감이 되어 영향력을 끼치지 못 하고...
그래서 재귀로 구현하는 것이 좋다는 것을 알게되었다.

📌Error 코드

def dfs(start, visit):

    cnt = 0
    visit[start] = True
    stack = [start]
    while stack:
        cnt += 1
        v = stack.pop()
        for i in card[v]:
            if not visit[i]:
                stack.append(i)
                visit[i] = True
            elif i == start and cnt >= 2:
                iscircular[start] = True
                return

📌수정한 code
cnt >= 2일 때 current가 start와 같게 된다면 순환역이라고 기록하고 함수 종료

def dfs(current, start, visit, cnt):


    visit[current] = True
    for i in card[current]:
        if not visit[i]:
            dfs(i, start, visit, cnt+1)
        elif i == start and cnt >= 2:
            iscircular[start] = True
            return

순환역을 저장해 주고 이를 기반으로 이제 BFS로 거리 측정을 함.
거리 측정을 할 때도 마찬가지로 리스트를 이용함. 우선 순환선에 대해서 먼저 처리를 해줄 필요가 있었음. 그래서 순환선에 loop를 따로 돌려서 거리를 저장해 줌. 그 다음에 모든 원소에 대해서 방문을 안 했다면 해당 노드 distance의 value를 하나 증가시켜며 queue에 넣어줬다.

def bfs():
    queue = deque([])
    distance = [-1] * (n+1)
    # 순환선 방문처리 및 거리 0으로 초기화
    for i in range(1, n+1):
        if iscircular[i]:
            distance[i] = 0
            queue.append(i)
    while queue:
        v = queue.popleft()
        for i in card[v]:
        	#방문하지 않았다면
            if distance[i] == -1:
                queue.append(i)
                distance[i] = distance[v] + 1
    
    print(*distance[1:])

전체 코드

import sys
from collections import deque
sys.setrecursionlimit(100000)

n = int(input())
card = [[] for _ in range(n+1)]

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    card[a].append(b)
    card[b].append(a)


def bfs():
    queue = deque([])
    distance = [-1] * (n+1)
    for i in range(1, n+1):
        if iscircular[i]:
            distance[i] = 0
            queue.append(i)
    while queue:
        v = queue.popleft()
        for i in card[v]:
            if distance[i] == -1:
                queue.append(i)
                distance[i] = distance[v] + 1
    distance = distance[1:]
    print(*distance)



def dfs(current, start, visit, cnt):


    visit[current] = True
    for i in card[current]:
        if not visit[i]:
            dfs(i, start, visit, cnt+1)
        elif i == start and cnt >= 2:
            iscircular[start] = True
            return

iscircular = [False] * (n+1)
for i in range(1, n+1):
    visit = [False] * (n + 1)
    dfs(i, i, visit, 0)

bfs()