9466 - 그룹찾기 (DFS,Stack)

초기 설계
1. for(x)문에서 케이스 배열을 순환하며 x를 start로 기억해서
이것과 같은 경우만 같은 그룹으로 생각하여 설계
2. n퀸 처럼 판단을 먼저 한 뒤에 값을 변경하고 싶었다.
ㄴ> 다만 이렇게 하면 같은 그룹에 속해있는지를 분간할 방법이 없음

초기설계에 대한 확실할 반례
1
5
2 3 4 5 4

1
3
2 3 2

일단 돌면서 자기 자신을 만났을 때만 그룹이 유효하지 않다.
화살표가 중간에 자기들끼리 연결되어 있는 경우가 있기 때문. >>> 초기1의 잘못된 경우

또한 서로가 서로를 가르키는 형국일때 초기설계는 값을 미리 변경하면서 판단하기 싫어서 기록하지 않았는데,
이러면 계속해서 Stack에 담게 된다.
4 5 4 5 이런식으로 >> 메모리초과
그렇게 하지 않고 그룹의 값을 주고 만들어지는 경우에 한 해 스택에서 뽑아내고
순환하지 않는 부분부터는 그룹화이 지정되지 않았음을 명시할 필요가 있었고

값을 계속넣어왔지만 사실상 스택에 다 담겨있으니 pop하면서 내가 담았던 값을 변경해주면 문제가 없을 것으로 생각하였음

구현

import sys

n = int(input())

case = [] #Like L
ansarr = []
for _ in range(n):
	k = int(input())	
	ansarr.append([0] * (k+1))
	case.append([0])
	case[_].extend(list(map(int,sys.stdin.readline().strip().split())))

def f_stack(L,arr):
	cnt = 0
	for ind in range(1,len(L)):
		if arr[ind]:
			continue
		st = ind
		stack = []
		stack.append(st)
		cnt+=1#스택을 다 덜어내야할때 증가한거에서 빼는게 맞나?
		arr[ind] = cnt
		while(stack):
			vec = L[stack[-1]]
			if arr[vec]: ##이런 판판단  중중에 arr이 이미 있으면 스택에 있는건 전부
				########################################################	
				if arr[vec] == arr[stack[-1]] : #while 2check rem vec!
					end = vec #유효한 그룹까지 기억할 필요가 있었음
					while(stack[-1]!=end):
						stack.pop()
					stack.pop() #end
					while(stack):
						temp = stack.pop()
						arr[temp] = 100010
				else:
					while(stack): #every to 100001
						temp = stack.pop()
						arr[temp] = 100010
					cnt-=1
			else:
				stack.append(vec)
				arr[vec] = cnt
	ans = 0
	for x in arr:
		if x == 100010:
			ans+=1
	return(ans)

for cind in range(n):
	print(f_stack(case[cind],ansarr[cind]))

메모리 초과일때 메모리 누수뿐 아니라,
무한루프격으로 계속 넣어주는 케이스가 있을 수가 있다는 점을 생각해야한다.

선 판단.후 방문(변경)이 항상 옳지만은 않았다.
DFS라고 해서 반드시 중간중간 값을 변경하지 않는 것은 아니다.