99클럽 코테 스터디 24일차 TIL + BFS(가장 먼 노드)

오늘의 과제

프로그래머스 Lv.3으로 분류된 가장 먼 노드입니다.

 

이번 유형은 BFS(넓이 우선 탐색, 그래프) 입니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

입력으로 n개의 노드와 왕복이 가능한 간선이 주어집니다. 이 때 , 1번 노드를 기준으로 가장 먼 노드의 갯수를

반환하면 됩니다.

 

이전에 BFS를 풀었듯 Queue를 활용하되, 새로운 개념인 그래프를 활용하는 문제입니다. 그래프를 활용하는 문제는 최초 변수 초기화에 주어진 vertex를 ArrayList를 통해 잘 셋팅해야 문제의 조건에 집중할 수 있습니다. 

 

이전 DFS 문제에서 풀었듯 순회하며 깊이를 체크 후 answer에 추가하고, 만약 더 깊은 곳으로 이동할 수 있다면

이전에 추가한 노드는 가장 깊은 곳이 아니였으니 answer를 초기화합니다.

 

 

코드입니다.

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    
    public int solution(int n, int[][] edge) {
        for(int i = 0 ; i <= n ; i++) graph.add(new ArrayList<>());
		
        // v => w로 이동할 수 있다
        // w => v로 이동할 수 있다.
		for (int[] i : edge) {
			int v = i[0];
			int w = i[1];
			graph.get(v).add(w);
			graph.get(w).add(v);
		}

		boolean[] visit = new boolean[n + 1];
        return bfs(graph, n, visit);
    }
    
    public static int bfs(ArrayList<ArrayList<Integer>> graph, int n, boolean[] visit) {
		Queue<int[]> q = new LinkedList<>();
		int answer = 0;
		
		q.add(new int[] {1, 0});
		visit[1] = true;
		int maxDepth = 0;
		
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			int v = arr[0];
			int depth = arr[1];
			
            // 기존에 파악한 최대 길이 노드라면 추가한다.
			if(maxDepth == depth) {
                answer++;
            // 기존에 파악한 최대 길이 노드보다 길다면 초기환한다.
            } else if (maxDepth < depth) {
				maxDepth = depth;
				answer = 1;
			}

			// 방문 여부를 확인해 노드의 깊이를 확인한다.
			for (int i = 0; i < graph.get(v).size(); i++) {
				int w = graph.get(v).get(i);
				if (!visit[w]) {
					q.add(new int[] { w, depth + 1 });
					visit[w] = true;
				}
			}
		}

		return answer;
	}
}

 

 

배운 점

 

기본 BFS 문제에서 그래프라는 자료구조를 추가한 문제였습니다. 이제 슬슬 기본 DFS, BFS를 조금 더 활용하는 문제들이 나올 것 같습니다. 그래프 기본 문제들로 시작하지만 곧 최단 경로 문제와 같은 코딩테스트 단골 문제들이 등장할텐데 이전과 같이 무너지지 않으려 학습해야겠습니다.

 

3주가 넘는 기간동안 진행하니 문제의 분류가 조금씩 쌓이고 있습니다. 문제에서 직접적으로 언급하지 않더라도 입력을 보고 시간 복잡도를 계산 후 풀이 방법을 선택하는 습관을 들여야 나중에 고생하지 않을 것 같네요.

 

 

오늘의 한줄평

빙글빙글 뱅글뱅글 신나는 그래프