2668(숫자고르기) - 해결

숫자고르기

 

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

 

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

 

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

---

이 문제의 핵심은 사이클을 찾는 문제였던거 같다.

이를 dfs로 구현하는데 여러 갈래로 갈라지는 것이 아니라서 stack으로 구현을 하였다.

기본 아이디어는 처음 시작 인덱스와 같은 수로 돌아 올 수 있는가를 보았다.

여기에서 조금 고민했던 것은 visit를 구현하는 것이였다. visit가 없다면 반복이 일어날것 같아서 혹시나 시간 초과가 날꺼 같아서 이를 해결하려고 하였다. 시간을 신경안쓴다면 모든 인덱스를 탐색하면서 자기 자신으로 돌아오는 인덱스를 찾아 1개씩 증가해서 하면 된다고 생각을 하였지만 이거보다는 시간을 줄여보고자 하였다. 

이를 구현하기 위해서 지나온 숫자들을 저장하였고 사이클을 찾으면 이 숫자의 방문을 체크하였다.

또한 자기자신의 인덱스와 숫자가 같다면 바로 숫자를 추가하였다.

import sys
input = sys.stdin.readline

# dfs 
def dfs(v):
    # 방문 숫자
    visit_num = [v]
    # 스택
    stack = [v]

    # 스택 탐색
    while stack:
        node = stack.pop()
        # 다음 숫자
        n_node = num_list[node]
        # 다음 숫자가 처음 숫자와 같으면 사이클이 생김
        if n_node == v:
            # 갯수는 방문 숫자의 갯수
            cnt = len(visit_num)
            # 중복을 제외하기 위해서 방문 체크
            for num in visit_num:
                visit[num] = 1
            # 갯수와 사이클에 속하는 숫자
            return (cnt,visit_num)
        
        # 만약 다음 숫자가 방문했던 숫자면 다음으로(결국 return 된다)
        if n_node in visit_num:
            continue
        # 아니라면 스택과 방문 숫자에 추가
        else:
            stack.append(n_node)
            visit_num.append(n_node)
    # 없아면 0과 빈 리스트 반환
    return (0,[])


N = int(input())

# 숫자
num_list = [0]
# 방문
visit = [0] * (N+1)
# 정답 리스트
ans_list = []

# 입력
for i in range(1,N+1):
    num_list.append(int(input()))
    # 인덱스와 숫자가 같으면 바로 방문 체크와 추가
    if i == num_list[i]:
        visit[i] = 1
        ans_list.append(i)
# 숫자와 인덱스가 같은 것은 미리 추가
max_v = sum(visit)

# 각 숫자마다 체크
for i in range(1,N+1):
    # 방문했는거면 다음으로
    if visit[i]:
        continue
    # dfs후 숫자와 리스트 받아오기
    cnt, n_list = dfs(i)
    # 숫자 추가와 리스트 추가
    max_v += cnt
    ans_list.extend(n_list)

# 정렬
ans_list.sort()

# 출력
print(max_v)
for i in ans_list:
    print(i)

 

그리고 그냥 각 숫자를 중복해서 방문하는 방법을 해보았다.

import sys
input = sys.stdin.readline

# dfs
def dfs(v):

    # 스택과 방문 숫자
    stack = [v]
    visit_num = [v]

    # 탐색
    while stack:
        node = stack.pop()
        
        n_node = num_list[node]
        
        # 다음 숫자가 방문 했는가?
        if n_node in visit_num:
            # 방문했는데 처음 숫자와 같은가
            if n_node == v:
                return v
            return 0
        # 스택과 방문 추가
        stack.append(n_node)
        visit_num.append(n_node)
    
    return 0
            
N = int(input())

num_list = [0]
ans_list = []
cnt = 0

# 입력
for i in range(1,N+1):
    num_list.append(int(input()))

# 전체 숫자 dfs
for i in range(1,N+1):
    # 0이 아닌 자신이 반환되면
    if dfs(i):
        # 해당 숫자는 사이클에 포함되기 때문에 
        # 갯수 추가와 숫자 추가
        cnt += 1
        ans_list.append(i)
# 출력
print(cnt)
for i in ans_list:
    print(i)