[Python] 백준 24479: 알고리즘 수업 - 깊이 우선 탐색 1

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

🔒

화려한 제출 내역

dfs를 완전히 이해하지 못한 상태에서 문제를 접근하니 힘들었던 것도 있지만, 추가적으로 고려해야 하는 조건이 있었고, 그 조건을 찾지 못해 정말 어려웠던 문제... 겨우 성공했으나 PyPy3이 아니라 Python으로 돌리면 시간 초과가 나는 점까지 참 한숨 나오는 문제였다.

코드 길이를 보면 재설계도 여러번 할 정도로 문제를 여러 차원에서 접근하고자 했다.

문제에서 고려할 점: 무방향 그래프(양방향 간선), 오름차순으로 방문, 방문할 수 없는 지점의 경우 0 출력, 방문 순서가 아닌 i번째 방문 순서를 출력

 

1차 시도

# 정점 번호는 1부터 N까지. m개의 다리. 오름차순. 방향 없음

n,m,r = map(int, input().split())
goal =[[] for _ in range(n+1)]
for i in range(m):
    ls = list(map(int,input().split()))
    v1 = ls[0]
    v2 = ls[1]
    goal[v1].append(v2)
    goal[v2].append(v1)

for i in goal:
    i.sort()

def dfs(v):
    stack = []
    ans = [0]*n
    visited = [False]*(n+1)
    stack.append(v)
    visited[v] = True
    cnt = 1
    ans[v-1] = cnt #첫번째로 가는 지점(함수에서 넣어준 값. tc에서는 1)
    while stack:
        for w in goal[v]: #goal[v]에서 연결된 w를 경유할 것
            if not visited[w]:
                cnt +=1
                visited[w] = True
                ans[w-1] = cnt
                stack.append(v)
                v = w
                break
        else:
            stack.pop()

    for i in ans:
        print(i)
dfs(r)

 

2차 시도

n,m,r = map(int, input().split())
goal =[[] for _ in range(n+1)]
ans = [0]*(n+1)
cnt = 1

for i in range(m):
    ls = list(map(int,input().split()))
    v1 = ls[0]
    v2 = ls[1]
    goal[v1].append(v2)
    goal[v2].append(v1)

for i in goal:
    i.sort() #오름차순 정렬

def dfs(v):
    global cnt
    ans[v] = cnt #초기에 들리는 정점
    for i in goal[v]:
        if not ans[i]: #ans[i]에 설정된 값이 없다면(방문 X)
            cnt+=1
            dfs(i)
            
dfs(r)
for i in ans[1:]:
    print(i)

 

3차 시도

N,M,R = map(int, input().split())

goal = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int, input().split())
    goal[a].append(b)
    goal[b].append(a)

for i in goal:
    i.sort()

res = [0] * (N+1)
# 정점의 방문 순서를 출력. 만일 방문 불가능하다면 0 출력
# print(goal)
def dfs(v):
    global res
    st = []
    visited = [False] * (N+1)
    st.append(v)
    visited[v] = True
    res[v]= 1
    cnt = 1
    while st:
        for w in goal[v]:
            if not visited[w]:
                visited[w] = True
                goal[v].pop()
                cnt += 1
                # print(w)
                res[w] = cnt
                st.append(v)
                v = w
                break
        else:
            v = st.pop()
    res = res[1:]
    for i in res:
        print(i)
    
dfs(R)

 

ANS

N, M, R = map(int, input().split())

goal = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    goal[a].append(b)
    goal[b].append(a)

for i in goal:
    i.sort()

res = [0] * (N + 1)
cnt = 1

# 정점의 방문 순서를 출력. 만일 방문 불가능하다면 0 출력
def dfs(v):
    global res
    global cnt
    st = []
    visited = [False] * (N + 1)
    st.append(v)
    visited[v] = True
    res[v] = 1
    #v와 연결된 원소 지우기
    while st:
        for w in goal[v]:
            if not visited[w]:
                visited[w] = True
                goal[v].pop(0)
                cnt += 1
                # print(w)
                res[w] = cnt
                st.append(v)
                v = w
                break
        else:
            v = st.pop()
    res = res[1:]
    for i in res:
        print(i)


dfs(R)

 

🔑

이 문제의 히든 조건은 1->2로 갈 때 1에서 2로 갈 수 있는 원소들을 지우는 것이다.

for문에서 w가 goal[v]의 맨 앞부터 차근차근 살펴보는데 막상 pop에 인덱스를 써넣어주지 않아 맨 뒤에 원소가 빠지게 되었다.  for문에서 pop(0)을 하면 잘(천천히) 돌아간다!