[백준] 2668 숫자고르기 (파이썬)

골드 Ⅴ

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

2668번: 숫자고르기

 

📄 문제

• 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다.
• 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고
• 둘째 줄의 각 칸에는 1 이상 N이하인 정수가 들어 있다.
• 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.

 

이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오.

 

---

💡 아이디어

 

• 위 그림을 참고하여 생각해 보면, 1 - 3을 뽑으면 3 -1을 뽑으면 된다.
• 5를 뽑으면 아래도 5가 존재하므로 다른 수를 더 찾을 필요 없다.
• 위의 표를 첫 번째 줄에서 두 번째 줄로 향하는 단 방향 그래프라고 생각하자.
• 첫 번째 줄의 출발 값과 두 번째 줄의 값이 같아지는 경우를 찾으면 처음 값으로 돌아와 사이클을 형성하게 된다.
• 즉, 사이클을 형성하면 첫 번째, 두 번째 줄 모두 같은 값을 선택한 것이다.

따라서, 이 문제의 포인트는 첫 번째 줄의 출발 값 = 두 번째 줄 값을 찾아 사이클을 형성하면 되는 것이다.

사이클을 찾는 함수를 생성하여 단 방향 그래프 탐색을 통해 시작 값으로 돌아올 수 있는 지를 탐색한다.

---

1. 첫 번째 줄의 값을 차례대로 출발 값으로 설정하여 사이클을 찾는 그래프 탐색을 수행한다.
2. 너비 우선 탐색(BFS) or 깊이 우선 탐색(DFS)을 활용하여 사이클을 찾는 함수를 생성한다.
   • 첫 번째 줄에서 단 방향 그래프의 출발 값(start)을 설정한다.
   • 출발 값을 시작으로 단방향 그래프를 따라 순서대로 그래프를 탐색한다.
   • 지나가는 숫자들을 모두 방문 체크(visited)한다. (visited에 지나는 값 저장)
   • 이미 지나간 숫자를 만났을 경우 탐색을 종료한다. (사이클 형성)
   • 출발 값과 같은 숫자를 만났을 경우에는 지나온 숫자(visited)들을 정답(ans)에 저장해 준다.
3. 지나온 숫자를 만나 함수를 종료시킬 때 어떤 숫자를 만났냐에 따라 2가지 경우로 구분된다.
4. 그래프 탐색을 통해 출발 값과 같은 숫자를 만났다는 것은 사이클을 형성한 것이다.
   • 이는 출발값과 같은 두 번째 줄의 값이 등장했다는 것이다.
   • 즉, 첫 번째 줄과 두 번째 줄에서 선택된 숫자가 모두 같다.
   • 첫 번째 줄의 값들은 1에서부터 n까지의 수로 모두 다르기 때문에 같은 값은 두 번째 줄에서만 등장할 수 있다.
   • 따라서, 선택된(거쳐간) 수들을 모두 ans에 저장한다.
5.  출발 값과 다른 숫자를 만났을 경우에는 지나온 숫자들을 정답(ans)에 저장하지 않고 종료한다.
   • 출발 값이 아닌 다른 점과 사이클이 형성되면 탐색을 종료한다.
   • 그래프를 탐색하는 과정에 있는 다른 수끼리와 사이클이 형성된 것이다.
6.  따라서, 방문한 지점을 다시 방문하게 되면 탐색을 종료한다.
7. 첫 번째 줄의 초기 값과 두 번째 줄의 값이 같아지는 경우가 존재하지 않는 경우에도 탐색을 종료한다.
8. ans의 길이와 저장된 값을 순서대로 출력한다.

 

예시

1	2	3	4	5	6	7
2	5	7	3	2	1	4

 

• 2 - 5 , 5 -2를 뽑으면 아래위의 수 모두 2, 5를 가지게 된다.
• 3 - 7, 4 - 3, 7 - 4를 뽑으면 아래위의 수 모두 3, 4, 7을 가지게 된다.

아래 그림으로 살펴보면 2 - 5 - 2, 3 - 7 - 4 - 3으로 사이클을 형성하는 것을 알 수 있다.

따라서, 우리는 1부터 n까지 수를 그래프 탐색하여 사이클을 형성하는 수들을 찾아주면 된다!

사이클 형성 ( 2 - 5 - 2 )(  3 - 7 - 4 - 3 )

 

📝 문제 풀이 (Code)

DFS를 활용한 코드

import sys
input = sys.stdin.readline

# 사이클 찾기 (그래프 탐색)
def dfs(v, start):
    global ans
	
    # 방문했으면
    if v in visited:
        # 사이클이면
        if v == start:
            # 사이클에 해당하는 수 저장
            ans |= visited
        return

    visited.add(v)
    # 연결된 그래프로 이동
    dfs(graph[v], start)


n = int(input())
# 인덱스 1부터 사용하기 위해 [0]추가
graph = [0] + [int(input()) for _ in range(n)]

# 둘째 줄에 들어있는 수들이 일치하면 저장(사이클이 존재하면 저장)
ans = set()
for i in range(1, n+1):
    # 방문 체크
    visited = set()
    # 사이클 확인
    dfs(i, i)

ans = sorted(ans)
print(len(ans))
for j in ans:
    print(j)

---

BFS를 활용한 코드

import sys
input = sys.stdin.readline

# 사이클 체크
def bfs(start):
    global ans
    # 방문 체크
    visited = set()
    # 한 개씩만 쌓인다.
    stack = [start]
    visited.add(start)

    while stack:
        v = stack.pop()

        # 연결된 그래프 숫자
        w = graph[v]
        # 방문했으면
        if w in visited:
            # 사이클이 존재하면
            if w == start:
                # 합집합
                ans = ans | visited
            return

        # 방문 안 했으면
        visited.add(w)
        stack.append(w)

    return


n = int(input())
graph = [int(input())-1 for _ in range(n)]

ans = set()
# 사이클이 존재하면 저장
for i in range(n):
    bfs(i)

print(len(ans))
for j in sorted(ans):
    print(j+1)