[BOJ] 9466번 - 텀 프로젝트

어제 SW마에스트로 코딩 테스트를 보면서 다시 한 번 좀 더 많은 문제를 풀어봐야겠다고 생각했다. 

자바 문법도 공부하고 있고, 창업 활동에서 했던 프로젝트 디자인 수정도 해야해서 정신이 없기도 하지만

알고리즘은 꼬박꼬박 푸는 중이다..

 

SW마에스트로도 몇 문제 더 풀었지만 알고리즘을 쓸 것 없이 완전 구현 문제였기 때문에 포스트를 굳이 하지 않기로 했다.

물론 구현 중 어려웠던 부분이 있더라면 쓰게 될 것 같다.

 

이번 문제에서는 dfs 부분(약한 부분이라 생각)의 문제를 한 번 풀어봤다.

70% 에서 시간 초과 계속 나서 결국 블로그들을 찾아 해결했다.. 

아직까지 어떤 부분에서 답지를 보며 스킬을 익히는것이 더 이득이고, 그렇지 않은 지 정확히 모르겠다.

어떤 사람은 답지를 보는게 좋다고 말하곤 한다.

 

어릴 때 수학문제나 과학문제 같은 것들을 풀어봤을 때, 답지 보는 것을 무지 싫어했다. 도저히 모르겠다면 답지를 보곤 했는데 그 과정까지 얻어간 것이 많았고, 결국 시험에서도 답지 없이 풀어나가니 웬만하면 안 보는게 맞다고 생각했다.

하지만, 알고리즘은 좀 틀린건가..? 싶기도 하다. 답지를 보는 것과 안 보는것 이 경계선을 아직 잘 모르겠다..

최선의 방법은 구현문제는 그냥 안 보고 디버깅하면서 풀고 나머지는 시간을 정해 놓고 답지를 봐야겠다고 생각했다.

 

 

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

1. dfs알고리즘을 이용하여 친구관계 사이클을 확인한다.

이어진 관계들을 check[] 배열을 통해 확인 해주면서 만약 check[]된 배열의 사람을 다시 확인 하게 된다면

사이클이 생긴다는 것을 알 수 있다.

 

2. 어디서부터 어디까지 사이클인지 확인하여 개수를 더하기 해준다.

 

1번 친구를 탐색 할 때

1번 친구를 dfs로 탐색한다 가정 할 때 4,6,2 친구의 사이클이 형성되는 것을 볼 수 있다. 

이 의미는 2,4,6번이 팀원이 될 수 있다는 말이되고, 이것을 알기 위해서는 사이클의 시작점을 알아야한다.

시작점을 알기 위해서는 1번 친구들의 데이터를 저장하는 list를 이용해 4번의 위치를 알아 낼 수 있다.

 

from sys import stdin, setrecursionlimit
from math import sqrt
setrecursionlimit(100000)
std = stdin.readline

T = int(std())
friend, check = [], []
stack = []
ans = 0


def dfs(a, b):
    global ans, check
    if check[b] == 1:
        if b in stack:
            ans += len(stack[stack.index(b):])
        return
    stack.append(b)
    check[b] = 1
    dfs(a, friend[b])


answer = []

while T > 0:
    T -= 1
    N = int(std())
    friend = list(map(lambda x: int(x)-1, std().split()))
    check = [0 for i in range(N)]
    ans = 0
    for i in range(N):
        stack = []
        if check[i] == 0:
            stack.append(i)
            check[i] = 1
            dfs(i, friend[i])
    answer.append(N-ans)

for a in answer:
    print(a)