[BOJ] 백준 13023번 : ABCDE (JAVA)

문제

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을 출력한다.

 

 

풀이

DFS를 이용하여 풀 수 있는 문제였습니다.

 

이 문제는 삽질할 요소가 굉장히 많았습니다. 먼저, 입력값을 보면 친구의 관계가 주어지는데 딱 이대로 인접리스트를 구현하지 않고 친구의 친구도 되겠구나하고 추가로 인접리스트를 조작하시면 안 됩니다. 가령, 0번과 1번, 2번, 3번이 친구라고 할 때, 1번은 0번이랑 친구니까 1번은 2번과 3번이랑도 친구구나하고 1번 리스트에 2번과 3번을 추가로 넣는 것이 아닙니다.

 

그리고 A와 B가 친구고, B와 C가 친구고, C와 D가 친구고 D와 E가 친구인 관계는 0 ~ N - 1까지의 노드 중에 일직선으로 연결된 노드가 5개가 있는지 확인하는 것과 동치합니다. 이것도 일반화하여 모든 노드가 일직선 상에 있는지 확인해야겠다고 오해하시면 안 됩니다.

 

마지막으로, dfs를 구현하실 때 주의할 점이 하나 있습니다. 만약, 0번 노드에서 시작하여 1번, 2번 노드까지 방문이 완료되었다고 합시다. 그렇다면, visited[0] = visited[1] = visited[2] = true이 상태인데, 더 갈 곳이 없다면 이대로 방문 정보를 냅두면 안 되고 모두 방문이 안 된 false 상태로 만들어야 합니다.

 

 

이렇게 3가지 주의 사항만 지킨다면, 전형적인 양방향 인접리스트와 dfs를 이용한 문제가 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.