9466번 - 텀 프로젝트
그림으로 먼저 그려보심이 어떠하실지요..
이 문제의 목표는 덩어리들에서 cycle을 검출하는 건데요.
예를 들어서
2 -> 3 -> 4 -> 6 -> 3 -> ... 이런 식으로 있다고 생각해 봅시다.
이 경우 dfs(2)가 먼저 호출이 될 텐데요. 이 때 visited[2] = 1이 됩니다.
여기서 visit는 2가지 역할을 하는데요.
하나는 방문했냐. 안 했냐?
또 하나는 방문했다면 몇 번째로 방문했느냐? 를 나타내는 겁니다.
그렇게 따지면 visit[3] = 2, visit[4] = 3, visit[5] = 4, visit[3] = ?
다시 3을 방문한 시점에서 cnt는 5가 됩니다. 그런데, 3부터 사이클이 시작된 건 맞습니다.
3은 몇 번째로 방문했냐. 2번째로 방문했습니다.
그렇기 때문에, 요소 내에 있는 사이클의 크기는 3이 되죠. 여기까지는 이해하셨나요?
자. 13번째 줄은 그러면
이전에 특정한 노드를 방문한 적이 있는가? 를 검사하는 것이죠.
그런데 dfs는 말이죠. 이 노드를 방문했었다가 참이 된다는 게.
사이클이 있다는 말입니다. 어딘가에.. 쉽게 생각해 보면..
2를 방문하고 4를 방문하고 6을 방문하고 그랬는데. 어느 순간 2를 방문한 꼴이 되거든요.. 어떻게 돌고 돌아서..
14번째 줄은 왜 있을까요?
예제의 그래프를 조금 변형해 봅시다.
2 -> 3 -> (1) <- 5
이 경우에는, 1이 사이클이 되어버립니다. 1 탐색은 여기서 끝나죠.
그 다음에는 2에서 출발하겠죠. 이 때 dfs 덩어리에서 start_node는 2가 됩니다. 2에서 탐색 시작했으니까요.
쭉 탐색을 해 봅시다.. 그런데 어느 순간 1을 방문하게 되는데요..
이미 1은 start_node가 1이네요. 2와 1이 다르네요..
만약에 이런 경우는 어떨까요?
1 -> 2 -> (3) <- 5
1에서 탐색을 시작하면 3까지는 갑니다. 그리고, 3이 사이클이기 때문에
1에서 시작하는 dfs덩어리에서 탐색이 시작되는 1과, 탐색이 끝나는 3의 first_location이 같죠.
이 두 경우를 구분지어 주기 위해서 14번째 줄이 있는 거죠.
2번 질문은 잘 모르겠네요..
원래 return 문 쓰는 게 맞지 않나? 라는 생각도 들고요. 자세한 건 뜯어봐야 알 거 같은데..
실제로 wandbox라는 컴파일러에서는
warning: control reaches end of non-void function [-Wreturn-type] }
요래 뱉더라고요.
이 부분에 대해서는 함수 호출 규약이라고..
Calling conversion을 참고해 보세요.
제가 봤을 때는 리턴하기 전에 특정한 (eax) 레지스터에 특정한 값을
저장하는 명령이 있기 때문에
답이 출력되기는 출력될 거 같긴 하네요. 심지어 dfs 함수를 호출하는 건 함수가 끝나기 직전에 있죠.
만약에 dfs 함수 내에 dfs 함수를 호출하는 부분이 있고
대입문이 여러개 있다면 그런 경우에는 장담을 못 할 거 같네요.
이런 것들의 특성상 산술 연산에 필요한 레지스터에다가 값을 집어넣고 빼기 때문에
레지스터에 있는 값들이 의도치 않게 업뎃이 될 거고.. 잘못된 값이 출력이 되겠죠.
실제로
24에서 25번째 사이에 아래와 같은 코드를 추가하면 wandbox에서는 잘못된 값을 뱉습니다.
return 문이 있는 함수인 경우..
리턴문이 없는 곳으로 가서 함수가 끝나버리는 경우 보통 경고가 뜰 겁니다. 저게 그 예죠.
결론은 리턴문이 있는 함수는
반드시 리턴을 해 주자에요. 그렇지 않으면 정의되지 않은 동작을 수행할 수 있어요.
약간 더 자세한 건 이쪽 참고하시는게..
댓글을 작성하려면 로그인해야 합니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
lmcoa15 6년 전
혼자서 해결하려다가 도저히 안되서 다른 분들이 하신거를 참고하여 코드를 작성했습니다.
소스코드를 간단하게 말씀드리면 ans는 사이클이 존재하는 것의 노드 개수이고
vec는 문제에 제시된 각각의 i번 별로 가리키는 node이고 visited는 방문을 확인함과 동시에 dfs를 돌때 몇번째로 방문했는지
나타내는 부분입니다. first_location은 dfs를 돌때 맨 처음에 전달한 시작 node를 각각의 위치에 저장해주는 부분입니다.
그리고 dfs함수내의 start_node는 처음 시작한 node, current_node는 호출할 때마다 가리키는 node이고
cnt는 현재 위치에서 이동할 때마다 몇번째로 방문했는지를 나타내기 위한 변수입니다.
우선 아래의 부분에서 dfs부분에서 사이클을 추려내기 위해 현재까지 이동한 지점에서 다음 노드의 visited값이 0이 아니면,
사이클이 존재한다고 가정하고 0이 아닌 부분의 visited값( 이전에 저장한 cnt값)을 빼서 사이클의 개수가
몇 개인지 구하는 방식은 이해했습니다.
하지만 이해가 되지 않는 부분은
첫번째 if문에서 first_location에 저장된 첫번째 노드를 왜 start_node와 비교하는지 이해가 되지 않습니다.
만약에 처음으로 dfs를 호출하면 매번 start_node를 first_location에 저장할텐데 굳이 start_node를 다시 비교해서 다르면
0을 리턴하는지... 분명히 반례가 존재해서 이렇게 하는거 같은데 이 부분에서 아마 막혀서 해결하지 못했던 것 같습니다.
혹시 그 이유를 알고 계시면 답변 부탁드리겠습니다. 그리고 마지막으로 dfs에서 if문 바깥에 보시면 그냥 dfs를 호출하는데
원래 return dfs(start_node, current_node, cnt + 1); 를 해줘서 값을 넘겨줘야 하는데 return 안해줘도 정상적으로
값이 나오더라구요.. 이부분도 좀 이해가 되지않는데 혹시 이유를 알고 계시면 답변 부탁드리겠습니다.
두서없이 써서 무엇을 물어보려는지 이해가 되지않으실까봐 그냥 요약해서 정리하면
1. dfs 함수의 if문 안에 존재하는 if문에서 first_location[current_node]와 start_node를 비교하는 이유
2. dfs 함수에서 마지막에 return dfs(start_node, current_node, cnt + 1);를 해줘야 하는데 그냥 dfs(start_node, current_node, cnt + 1);
를 써도 답이 출력되는 이유
입니다.