[Python] 백준 #2668- 숫자고르기

문제

---

 

2668번: 숫자고르기

코드

---

My answer

import sys
from collections import deque

input = sys.stdin.readline

N=int(input())
graph=[int(input()) for _ in range(N)]
graph.insert(0,0)
visit=[0 for _ in range(N+1)]

def dfs(idx):    
    if(visit[graph[idx]]==0):
        visit[graph[idx]]=1
        tmp.append(graph[idx])    
        dfs(graph[idx])
    else:
        return 0   
    
answer=set()
for i in range(1,N+1):
    visit=[0 for _ in range(N+1)]
    tmp,visit[i]=[i],1
    dfs(i)
    selected=[graph[j] for j in tmp]
    print(tmp)
    tmp.sort() 
    selected.sort() 
    if(tmp==selected): 
        answer.update([j for j in tmp])
     
answer=list(answer)
answer.sort()
print(len(answer))
for i in answer:
    print(i)

Another answer

import sys
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    adj[i].append(int(input()))

def dfs(num):
    if visited[num] == False:
        visited[num] = True
        for a in adj[num]:

            tmp_up.add(num)
            tmp_bottom.add(a)

            if tmp_up == tmp_bottom:
                ans.extend(list(tmp_bottom))
                return

            dfs(a)
    visited[num] = False

ans = []

for i in range(1, N + 1):
    visited = [False] * (N + 1)
    tmp_up = set()
    tmp_bottom = set()

    dfs(i)

ans = list(set(ans))
ans.sort()

print(len(ans))
for a in ans:
    print(a)

풀이

---

이번 문제의 경우 코드 짜는 것은 간단했는데 아이디어를 정리하는 것이 시간이 걸렸다.

우선 풀이부터 설명하자면, 첫째 줄의 경우 1~N까지 순서대로 정렬되어있기 때문에 따로 리스트에 넣어주지 않았고, 두번째줄 카드의 숫자만 그래프로 생성해줬다. 우선 BFS와 DFS 중 어느 알고리즘을 써야할지 생각하다가, 첫번째에서 뽑은 카드집합과 마지막에서 뽑은 카드집합의 비교를 위해서는 우선 카드를 다 뽑아야 비교가능했다. 따라서 dfs알고리즘을 쓰기로했다. 우선 방법은 첫번째줄 카드를 뽑는 것부터 dfs알고리즘을 실행한다. 첫번째줄 카드를 뽑으면 반드시 바로 아래줄 카드를 뽑아야하고, 조건을 만족시키기 위해서는 그 두번째줄에서 뽑은 숫자에서 이어지는 첫번째 수를 뽑아야했다. 

정리하자면, 첫번쨰를 뽑고 그 밑에있는 두번째를 뽑고 그 두번째와 똑같은 숫자를 다시 첫번째에서 뽑고 이걸 반복하면서 못뽑게될시 멈춰줬다.  이런식으로 알고리즘을 짜고 뽑은 첫번째 카드들만 나열해봤을 떄 아래와 같게 된다.

첫 리스트 [1,3]은 첫째줄 1을 뽑아서 바로 밑줄 3을 뽑게되고 그거랑 이어지는 3을 또 첫째줄에서 뽑고 그 밑에 있는 1을 뽑게되고 종료된다. 또 하나의 예시 맨마지막을 들어보면 7번을 뽑아서 그 밑 6번이 뽑히고 그 6번 밑에있는 4번이 뽑히고 4번 밑에있는 5번을 뽑고 5번 밑에있는 5번을 뽑으면서 종료된다.

단 위에까지 실행한 결과는 단순하게 계속하여 뽑은 것이고, 조건을 만족시키기 위해서 뽑은 첫쨰줄 숫자들과, 뽑은 두번째줄 숫자들이 일치하는지 확인해줘야한다. 따라서 현재 dfs알고리즘을 거쳐서 tmp라는 리스트안에 뽑은 첫째줄 숫자들이 기록되어있고, 아래 코드를 통해 selected에는 두번째 뽑힌 숫자들이 기록된다. 이후 위에 숫자와 아래 숫자가 모두 일치하는 경우가 조건에 만족하기 때문에 저장을해줘야하는데 위의 리스트에서 봤듯이 [1,3]과 [3,1]등 중복되기 때문에 집합으로 생성해서 업데이트 해준다. 

+) 마지막 답 제출시 문제 조건에 따라 반드시 정렬을해줘야한다. 처음에 나는 정렬하고 넣었기 때문에 마지막 answer을 다시 정렬하지 않고 제출했었는데, 집합의 경우 순서가 없기 때문에 꼭 마지막에 answer집합을 정렬하고 답안을 제출해야한다...반례들이 우연하게 모두 순서가 맞아서 계속하여 답이 맞는데 틀렸습니다가 떴었다 ㅠㅠ

selected=[graph[j] for j in tmp]

 print(tmp)

 tmp.sort()

 selected.sort()

 if(tmp==selected):

       answer.update([j for j in tmp])

another answer은 마지막에 비교하는 것이 아니라 dfs내부에서 중간중간 확인해주는 것이다. 

 

주저리주저리 써서 모르는 거 있으면 댓글 남겨주시면 최대한 아는대로 설명해보겠습니다.