[BOJ / 백준] 2668 숫자고르기 (G5^ / DFS) - Python

링크

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

 

 

 

 

문제 해석

세로로 2칸, 가로로 n개의 칸으로 이루어진 표가 주어짐
첫 번째 행에서 뽑은 숫자의 집합과, 첫 번째 행과 같은 열에서 뽑은 두 번째 행의 숫자의 집합이 동일해야 함

위를 만족하며 최대로 구할 수 있는 숫자 개수는?

 

 

 

입력
첫 번째 줄 : n
  n : 숫자의 개수

n개의 줄 : 2번째 줄에 들어갈 숫자

 

출력 
뽑힌 정수의 개수를 출력
뽑힌 정수들을 오름차순으로 출력

 

 

 

 

풀이 & 코드 해석

문제의 예제를 그려보면 위와 같습니다.

 

정답은 1, 3, 5인데 결국 사이클을 가지는 경우, 즉 나 자신으로 돌아올 방법이 있는 경우 정답이 된다는 것을 알 수 있습니다.

 

사이클의 종류는 크게 1과 3이 이루는 1대1 사이클, 5와 같이 단독 사이클, 그리고 아래에서 보여드릴 여러 숫자로 이루어진 사이클 등이 있을 수 있습니다.

 

 

 

위와 같은 그림 역시 나 자신으로 돌아오는 경로를 가지는 사이클입니다.

 

모든 숫자가 자신으로 돌아올 방법을 가지기 때문에 위 그래프의 정답은 1, 2, 3이 되겠죠.

 

 

 

결국 우리는 나 자신으로 돌아오는 사이클을 가지는지를 확인하고, 만약 돌아올 수 있다면 그 숫자를 정답으로 처리하는 코드를 작성하면 됩니다.

 

 

 

 

코드

def dfs(idx, target):
    v[idx] = True

    for i in graph[idx]:
        if i == target:
            ans.append(i)
            break

        if v[i] == True:
            continue
        dfs(i, target)

    v[idx] = False


n = int(input())

graph = [[] for _ in range(n + 1)]

v = [False] * (n + 1)

ans = []

for s in range(1, n + 1):
    e = int(input())

    graph[s].append(e)


for i in range(1, n + 1):
    dfs(i, i)

print(len(ans))
ans.sort()
for i in ans:
    print(i)

 

 

 

 

발생한 문제 & 해결 방안

처음에는 1대1을 만족하는 경우만 확인해서 틀렸다.

 

스스로 사이클을 만드는 케이스, 여러 숫자를 거쳐서 사이클을 만드는 케이스도 모두 확인해야만 문제를 해결할 수 있었다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java