[골드 5] 13023번: ABCDE

Original Source: https://www.acmicpc.net/problem/13023

13023번: ABCDE

---

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

---

사고의 흐름

• 우선 Input을 받은 다음 인접 리스트로 그래프를 표현해야겠다.
• 2차원 리스트 Input을 순회하면서 원소, 즉 1차원 리스트의 값을 인접 리스트에 추가하면 되겠지?
• 리스트 안의 첫 번째 원소 값을 두 번째 원소가 저장될 인덱스로 쓰고, 마찬가지로 두 번째 원소 값을 첫 번째 원소가 저장될 인덱스로 쓰면 되겠다.
• 깊이를 측정해서 값을 리턴해줘야 하니까 원래 DFS 함수에다가 카운트 매개변수를 추가해서, 재귀함수가 호출될 때마다 값을 하나씩 올려야겠다.
• Flag를 만들어서 DFS 함수가 카운트 매개변수를 리턴해 주었을 때 값이 4 이상이면 True로 바꾸면 될 듯?
• Visited[] 리스트를 DFS 함수를 최초 호출할 때마다 모두 False로 초기화해야 하나?
• 맞네, 가변 객체를 넘기면 참조 호출되어서 값이 바뀌는구나.

 

• 재귀 함수를 호출하면서 카운트를 세줘야 하는 건 알겠는데, 어느 부분에서 세야 할지 잘 모르겠다. 재귀 함수 동작하는 방식이 아직 잘 이해가 안 된다.
• 무작정 재귀 함수를 다시 호출할 때마다 카운트를 올리면, 하나의 노드에 두 개의 노드가 연결되어 있을 때 먼저 한 개의 노드에 들어갈 때 카운트가 오르고, 다시 나와서 다른 노드로 들어갈 때 카운트가 중복으로 올라간다. 이러면 안 되는데.
• 그러면 깊은 노드에서 얕은 노드로 나올 때 다시 카운트를 감소시키고, 대신 최댓값 변수를 하나 만들어서 카운트의 최댓값을 저장해야겠다. 그렇게 해서 최댓값 변수를 리턴시켜주면 되겠지.
• 최댓값 변수를 리턴하려면 재귀 함수가 호출되는 중에 문제 조건을 만족했을 때 바로 리턴을 해야 한다. 그렇지 않으면 스택에 쌓였던 재귀 함수들이 하나씩 pop되면서 최신의 최댓값 변수가 이전의 최댓값 변수로 대체되어버린다. 이럴 거면 차라리 카운트만 세다가 카운트가 4 이상이면 바로 리턴시켜버리는 게 맞는다.

 

• 잘 모르겠다;; 포기

남이 작성한 소스코드

Kyun2da 님:
https://kyun2da.github.io/2020/09/21/ABCDE/

피드백

• 파이썬에서 리스트는 함수로 넘겨줄 필요가 없다. 리스트는 Mutable한 객체이기 때문이다.
• 깊이를 카운팅할 때는 재귀 함수의 매개변수로 넘겨주는 방법이 가장 깔끔하다.
• 재귀 함수에서 리턴을 하면 상위의 함수에서 리턴 값을 저장하지 않는 한 그대로 사라진다. 대신 결과값을 출력한 뒤 sys.exit(0) 메서드를 사용해 바로 프로그램을 종료하자.

참고 자료

• https://www.pymoon.com/entry/Python-%EC%9D%80-callbyvalue-%EC%9D%BC%EA%B9%8C-callbyreference-%EC%9D%BC%EA%B9%8C
• https://wikidocs.net/91520