안녕하세요. 오늘은 프로그래머스의 가장 먼 노드 문제를 풀어보겠습니다.
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/49189
문제 풀이
1) DFS 풀이- 설명
선언한 변수
1. graph
- 각각의 노드들을 담는 이중 ArrayList
- 시작노드 / 끝노드 로 이루어짐
2. visited
- dfs 함수를 돌면서 각 노드를 방문했는지 여부를 체크
- 초기 선언 값 false
3. distance
- 노드1에서 노드n까지의 거리
- 초기 선언 값 int max value
- dfs 함수를 돌면서 cnt값과 distance값 비교 후 작은 값으로 input
핵심 코드
void dfs(int start, int cnt) {
//distance에 기존 distance값과 cnt값 중 더 작은 값 넣기
distance[start] = Math.min(distance[start], cnt);
for(start노드와 연결된 다른 노드들 탐색) {
if(node를 방문하지 않았다면) {
visited[node] = true;
dfs(node, cnt + 1); //node 탐색
visited[node] = false; //모든 경우의 수를 탐색하기 위해
}
}
}2) BFS 풀이 - 설명
선언한 변수
1. graph
- 각각의 노드들을 담는 이중 ArrayList
- 시작노드 / 끝노드 로 이루어짐
2. visited
- dfs 함수를 돌면서 각 노드를 방문했는지 여부를 체크
- 초기 선언 값 false
핵심 코드
int bfs() {
//bfs 탐색 위한 queue 선언
Queue<Integer> queue;
//queue에 시작점인 1 넣고, visited[1]= true
while(true) {
//temp 큐 선언
Queue<Integer> temp;
while(queue가 비어있지 않으면){
int cur = queue의 가장 앞쪽 값
for(graph 노드와 연결된 다른 노드(변수명 node)들 탐색){
if(node를 방문하지 않았다면) {
temp.offer(node); //temp 큐에 node 넣기
visited[node] = true; //node를 방문했다고 변경
}
}
}
//temp 큐에 아무것도 들어있지 않을 때까지 반복
if(temp 큐가 비어있다면) break;
}
}
전체 코드
1) DFS - 시간초과
import java.util.ArrayList;
class Solution {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
boolean[] visited;
int[] distance;
public int solution(int n, int[][] edge) {
visited = new boolean[n+1];
distance = new int[n+1];
int answer = 0;
for (int i = 0; i <= n; i++) {
graph.add(i, new ArrayList<>());
distance[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < edge.length; i++) {
graph.get(edge[i][0]).add(edge[i][1]);
graph.get(edge[i][1]).add(edge[i][0]);
}
dfs(1,0);
int max = 0;
for (int i = 2; i <= n; i++) {
max = Math.max(max, distance[i]);
}
for (int i = 2; i <= n; i++) {
if (distance[i] == max) {
answer++;
}
}
return answer;
}
private void dfs(int start, int cnt) {
distance[start] = Math.min(distance[start], cnt);
for (int node : graph.get(start)) {
if (!visited[node]) {
visited[node] = true;
dfs(node, cnt + 1);
visited[node] = false;
}
}
}
}2) BFS - 정답!
import java.util.*;
class Solution {
boolean[] visited;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
public int solution(int n, int[][] edge) {
visited = new boolean[n+1];
int answer = 0;
for (int i = 0; i < n + 1; i++) {
graph.add(i, new ArrayList<>());
}
for (int i = 0; i < edge.length; i++) {
graph.get(edge[i][0]).add(edge[i][1]);
graph.get(edge[i][1]).add(edge[i][0]);
}
answer = bfs();
return answer;
}
private int bfs(){
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
visited[1] = true;
int cnt = 0;
while(true) {
Queue<Integer> temp = new LinkedList<>();
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int node : graph.get(cur)) {
if (visited[node] == false) {
temp.offer(node);
visited[node] = true;
}
}
}
if (temp.isEmpty()) break;
queue.addAll(temp);
cnt = temp.size();
}
return cnt;
}
}느낀점
처음에 dfs로 풀어야겠다 생각하고 2시간동안 풀다가 결국 못풀었다.(시간초과가 난 게 아니라 아예 답이 틀렸었다..) graph변수에 node값을 집어 넣은 후 dfs를 돌렸지만 dfs함수가 잘못되었던 건지 답이 자꾸 다르게 나왔다. 다음엔 다른 사람의 코드를 참고하지 않고도 문제를 풀 수 있도록 노력해야겠다!
Backend Developer