백준 2688 숫자고르기 파이썬

풀이

순환여부를 물어보는 문제이다.
dfs로 탐색하면서 방문여부를 통해 문제를 풀 수 있었다. 너무 오랜만에 그래프탐색을 해서 그런지 문제이해하는데만 40분넘게 걸린 것 같다..ㅠ

입력부

n = int(input())
arr = [[] for i in range(n + 1)]
for i in range(1, n + 1):
    arr[i].append(int(input()))

각 칸에 맞게 배열들을 집어넣는다.

result = []
for i in range(1, n + 1):
    visited = [False] * (n + 1)
    dfs(i, i)

빈 배열을 만들어주고 dfs를 돌아준다.
여기서 dfs(i,i)는 확인하는 배열의인덱스를 접근하기 위한 첫번째 i와 1~N까지의 번호를 접근하기위한 i이다.

함수구현부

def dfs(a, b): #a : 배열의 인덱스접근, b : 1~N에 접근하기 위한 번호
    visited[a] = True
    for x in arr[a]:
        if not visited[x]:
            dfs(x, b)
        elif visited[x] and x == b:
            result.append(x)

visited[a]를 방문의 의미로 True를 넣어준다.
다음 배열에 접근해 리스트 안에 있는 x가 아직 방문을 안했다면
x,b를 다시 dfs를 돌려준다.
이후 visited[x]가 True거나 (한번더 방문했음을 의미)
x == b 이면 -> 자기자신 순환
result에 옮겨준다.

코드전문

def dfs(a, b):
    visited[a] = True
    for x in arr[a]:
        if not visited[x]:
            dfs(x, b)
        elif visited[x] and x == b:
            result.append(x)


# 입력부===========================
n = int(input())
arr = [[] for i in range(n + 1)]
for i in range(1, n + 1):
    arr[i].append(int(input()))
# ================================


# 출력부 ===========================
result = []
for i in range(1, n + 1):
    visited = [False] * (n + 1)
    dfs(i, i)
print(len(result))
result.sort()

for k in result:
    print(k)
# ================================

요즘 초등부 문제를 풀고 있는데 어렵다기 보다는 배웠던 내용을
자꾸 까먹는다... 복습은생명!