[프로그래머스(Programmers)] 가장 먼 노드 (java, BFS)

fantastik·2021년 8월 8일
1
post-thumbnail

안녕하세요. 오늘은 프로그래머스의 가장 먼 노드 문제를 풀어보겠습니다.


문제 링크

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함수가 잘못되었던 건지 답이 자꾸 다르게 나왔다. 다음엔 다른 사람의 코드를 참고하지 않고도 문제를 풀 수 있도록 노력해야겠다!


[참고한 곳]
https://velog.io/@hammii/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-java

0개의 댓글