문제
풀이
public class Q13023_ABCDE {
// 노드 간 관계를 표현할 배열
static LinkedList<Integer>[] arr;
// 방문 여부를 체크할 배열
static boolean[] visited;
// 관계의 깊이가 5이상인지 아닌지 체크할 변수
static int result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int node = Integer.parseInt(st.nextToken());
int edge = Integer.parseInt(st.nextToken());
arr = new LinkedList[node];
visited = new boolean[node];
result = 0;
for (int i = 0; i < node; i++) {
arr[i] = new LinkedList<>();
}
// 인접 리스트로 관계 표현하기
for (int i = 0; i < edge; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
// 관계간의 순서가 따로 정해져 있지 않으므로 각 노드를 서로의 배열에 저장
arr[s].push(e);
arr[e].push(s);
}
for (int i = 0; i < node; i++) {
// 시간복잡도를 위해 result가 1이라면 더 이상 반복읋 하지 않음
if (result == 1) {
break;
}
if (!visited[i]) {
dfs(i, 1);
}
}
System.out.println(result);
}
public static void dfs(int node, int depth) {
// 깊이가 5라면 더 탐색을 하지 않고 return
if (depth == 5) {
result = 1;
return;
}
visited[node] = true;
for (int i : arr[node]) {
// 저장중인 노드가 방문하지 않은 노드일 경우에만 재귀함수 호출
if (visited[i] == false) {
// 깊이 + 1
dfs(i,depth + 1);
}
}
// 이 로직까지 왔다는 뜻은 재귀함수를 통해 연결된 끝 노드까지
// 탐색을 마쳤다는 뜻이므로 다른 경우의 수를 위해 방문 기록을 false로 초기화
visited[node] = false;
}
}리뷰
먼저 문제는
a-b
b-c
c-d
d-e
가 친구인 경우를 구하는 문제였다.
a-b-c-d-e가 친구인 여부를 구하라는 것인데, 이걸 깊이로 따져보면 a~e까지는 5라는 깊이를 가지게 되고 우리는 깊이가 5인 경우의 수를 찾으면 된다.
따라서 DFS를 이용해서 풀면 되는 문제였다.
먼저 기본적인 dfs를 구현을 했고 깊이가 5가 되면 종료되는 로직까지 완료하였는데 자꾸 실패가 떴다.
내가 놓친 부분은 각 경우의 수에서 끝까지 탐색을 완료하였으면 방문 기록을 리셋을 시켜줬어야 했는데 이것을 해주지 않아 문제가 자꾸 틀린것이었다ㅜㅜ
이 문제에서 내가 놓친 문제는 2가지였다.
- 방문 기록 초기화하기
이 문제에서 엣지로 이어진 노드들은 순서가 정해져 있지 않기 각 노드에 따라 생기는 경우의 수는 각각 달라진다.때문에 연결된 노드의 마지막 노드까지 탐색을 마쳤다면 앞서 기록했던 방문 기록을 다시 false로 바꿔줘야 한다.
예를 들어 아래의 그림에서
0-4-7-3-7를 탐색을 하였다면 해당 노드들은 방문을 한것으로 체크되어 있을 것이다.
따라서, 그 이후의 재귀호출에서 0-4-3순서로 탐색을 한다고 하면 이 노드들은 방문을 한 것으로 체크되어 있지 때문에 탐색 진행하지 않고 함수 호출을 끝내게 된다.
각 시작점에 따라 깊이가 5인 경우의 수를 구하기 위해서는 한번의 사이클이 끝난 후에는 방문 여부를 false로 초기화해줘야 한다.
- 반복문 종료시점 설정해주기
main메서드에서 dfs를 호출할 때 이미 앞선 반복에서 깊이가 5인 경우의 수가 나왔다면 굳이 남은 반복문을 수행하지 않고 수행을 종료해주는 쪽이 수행시간 측면에서 효율적인데, 이 부분을 해주지 않아 시간초과가 발생하였다.
알고리즘 문제를 풀 때마다 느끼는게 아무리 알고리즘 이론을 알고 있어도 알고리즘을 적용하는 것은 별개라는 것이다ㅜㅜ 꾸준히 풀다보면 점점 나아지겠지..?
