Graph: 백준 경로찾기 - 11403

문제 유형: Graph - Floyd Warshall

작성 코드

첫 번째 시도

package KakaoCodingStudy.kakaoNov3;

import java.util.*;

// First Try BFS
public class Main3 {
    static int N;

    static Map<Integer, List<Integer>> nodeMap;
    static int[][] board;
    static int[][] answer;

    public static void input(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        board = new int[N][N];
        answer = new int[N][N];
        nodeMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            nodeMap.put(i, new ArrayList<>());
        }
        sc.nextLine();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (sc.nextInt() == 1) {
                    nodeMap.get(i).add(j);
                    nodeMap.get(j).add(i);
                    board[i][j] = 1;
                }
            }
        }
    }

    public static void pro(){
        for (int i = 0; i < N; i++) {
            bfs(i);
        }
    }

    public static void bfs(int from) {
        Deque<Integer> bfsQueue = new LinkedList<>();
        bfsQueue.add(from);
        int[] visited = new int[N];

        while (!bfsQueue.isEmpty()) {
            int node = bfsQueue.pollFirst();
            List<Integer> toNodes = nodeMap.get(node);


            for (int to : toNodes) {
                if (visited[to] == 0) {
                    visited[to] = 1;
                    bfsQueue.add(to);
                }
            }
        }
        System.out.println(Arrays.toString(visited));
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

두 번째 시도

package KakaoCodingStudy.kakaoNov3;

import java.util.Scanner;

// Second Try - Floyd Warshall
public class Main31 {
    static int N;
    static int[][] nodeMap;
    public static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nodeMap = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                nodeMap[i][j] = sc.nextInt();
            }
        }
    }

    public static void pro() {
        floydWarshall();
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer.append(nodeMap[i][j]).append(" ");
            }
            answer.append("\n");
        }
        System.out.println(answer);
    }

    public static void floydWarshall(){
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (nodeMap[i][k] == 1 && nodeMap[k][j] == 1) {
                        nodeMap[i][j] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

접근방식

예시를 바탕으로 처음에는 BFS도 가능성이 있다는 생각이 들었다. 물론 불가능해서 결론적으로는 Floyd Warshall을 사용했다. 기본적인 알고리즘을 물어보는 코딩테스트에 관련해서는 알고리즘 자체를 바꾸기보다는 주어진 값을 활용하는 방식이 많기에 예시를  BFS에서 처리하는 형식으로 바꿔 보았다. 하지만 어디선가 잘못됐는지는 확실하게는 모르겠으나 간단하게 Floyd Warshall을 활용하여 풀었다.