[프로그래머스] 49189 가장 먼 노드(Level3) - 그래프, BFS

문제

코드

시도1 - 인접 행렬 구현 X

백준 미로 탐색 문제(https://tojaman.tistory.com/81) - 그래프)의 풀이 방식에 최댓값의 개수를 구하는 코드를 추가하여 풀었다.

솔직히 왜 틀린건지 모르겠다... 일단 넘어간다.

import java.util.*;

class Solution {
    int[][] graph;
    Queue<int[]> q = new LinkedList<>();
    boolean[][] visit;
    int[][] move;
    public int solution(int n, int[][] edge) {
        graph = new int[n+1][n+1];
        visit = new boolean[n+1][n+1];
        move = new int[n+1][n+1];

        for (int i = 0; i < edge.length; i++) {
            graph[edge[i][0]][edge[i][1]] = 1;
            graph[edge[i][1]][edge[i][0]] = 1;
        }

        bfs(1, 1, n);
        int max = 0;
        int count = 0;
        for (int i = 1; i < n+1; i++) {
            for (int j = i; j < n+1; j++) {
                if (max < move[i][j]) {
                    max = move[i][j];
                    count = 1;
                }
                if (max == move[i][j])
                    count++;
            }
        }
        return count;
    }

    public void bfs(int x, int y, int n) {
        q.add(new int[] {x, y});
        visit[x][y] = true;
        move[x][y] = 1;

        int dx[] = {0,1,0,-1};
        int dy[] = {1,0,-1,0};

        while(!q.isEmpty()) {
            int[] now = q.poll();
            int nowx = now[0];
            int nowy = now[1];

            for (int i = 0; i < 4; i++) {
                int nextx = nowx + dx[i];
                int nexty = nowy + dy[i];
                if (nextx < 0 || nexty < 0 || nextx > n || nexty > n)
                    continue;
                if (graph[nextx][nexty] == 1 && visit[nextx][nexty] == false) {
                    q.add(new int[] {nextx, nexty});
                    visit[nextx][nexty] = true;
                    move[nextx][nexty] = move[nowx][nowy] + 1;
                }
            }
        }


    }
}

시도2 - 인접 행렬 구현 X

visit, distance를 1차원 배열로 선언하고 q의 요소를 int[]에서 Integer로 간소화하여 작성한 코드이다. 전형적인 BFS 코드이고 아래 그림처럼 작동한다.

import java.util.*;

class Solution {
    int[][] graph;

    public int solution(int n, int[][] edge) {
        graph = new int[n+1][n+1];

        // 그래프 인접 행렬 생성
        for (int i = 0; i < edge.length; i++) {
            graph[edge[i][0]][edge[i][1]] = 1;
            graph[edge[i][1]][edge[i][0]] = 1;
        }

        // 최단 거리 구하기
        int[] distance = bfs(1, n);

        // 가장 먼 거리를 찾고, 그 거리의 노드 개수 세기
        int maxDistance = 0;
        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (distance[i] > maxDistance) {
                maxDistance = distance[i];
                count = 1;
            } else if (distance[i] == maxDistance) {
                count++;
            }
        }

        return count;
    }

    public int[] bfs(int start, int n) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visit = new boolean[n + 1];
        int[] distance = new int[n + 1];

        q.add(start);
        visit[start] = true;

        while (!q.isEmpty()) {
            int current = q.poll();

            for (int i = 1; i <= n; i++) {
                if (graph[current][i] == 1 && !visit[i]) {
                    q.add(i);
                    visit[i] = true;
                    distance[i] = distance[current] + 1;
                }
            }
        }

        return distance;
    }
}

• 큐

• visit[]

• distance[]

시도3 - 인접 리스트 구현 O

인접 리스트로 구현한 코드이다.
코드 로직은 시도 1, 2와 동일하다.

import java.util.*;

class Solution {
    ArrayList<Integer>[] graph;
    int[] distance;

    public int solution(int n, int[][] edge) {
        graph = new ArrayList[n + 1];
        distance = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] e : edge) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        bfs(1, n);

        int maxDistance = 0;
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] > maxDistance) {
                maxDistance = distance[i];
                count = 1;
            } else if (distance[i] == maxDistance) {
                count++;
            }
        }

        return count;
    }

    private void bfs(int start, int n) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int next : graph[current]) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                    distance[next] = distance[current] + 1;
                }
            }
        }
    }
}

• graph[][]

• q

• visit

• distance