[백준] no11403: 경로 찾기

문제

주어진 매트릭스를 보고 이동 가능한 경로가 있는지 파악하는 것이다.

각 좌표의 x, y는 '출발지점, 도착지점' 이라고 보면 된다.

출발지점부터 목표지점으로 이동이 가능하면 1, 불가능하면 0으로 표기하면 된다.

예를들어 0->1 ,1->2, 2->0으로 가는 길이 있다고 할 때, 0에서 0으로 가는 방법은 0->1->2->0이 있으므로 가능

단, 0->0과같이 제자리 이동만 있는 경우는 0이다.

 

문제 링크 : https://www.acmicpc.net/problem/11403

---

원리

1. 재귀적 반복 : 삼중반복 + 재귀

2. 그래프 탐색

---

나의 코드

1. 재귀적 반복 [ 로컬 성공 | 백준 시간 초과]

: 각 좌표에 대해 경우의 수를 재귀로 반복한다.

: 이동이 가능한 경로일 때, 방문한적이 없다면, 방문 체크 하고 이동한다.

: 이동 후 해당 위치에서 다시 모든 가능한 이동 경로를 확인해서 반복 이동한다.

: 이동중 만약 목적지점과 현재지점이 같다면, 처음 출발지점-목표지점 좌표는 1이 된다

* 핵심 : 출발지점과 목표지점이 같은 경우, 제자리 이동을 제외시킬 수 있어야 한다.

  필자는 visitedStack이라는 변수를 선언해서 값이 true일때 경로 이동을 인정해주는 방법으로 사용했다.

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class no11403 {
    static int T;
    static Integer[][] matrix;
    static boolean[][] visited;
    static boolean visitedStack;
    static int[][] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 맵 구성
        T = Integer.parseInt(br.readLine());
        matrix= new Integer[T][T];
        for(int i=0; i<T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<T ; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        result = new int[T][T];

        for(int y=0; y<T ; y++) {
            for(int x=0; x<T ;x++) {
                if(result[x][y]==1) continue;
                visited = new boolean[T][T];
                visitedStack= false;
                search(x,y,x);

            }
        }

        for (int i=0; i<T ; i++) {
            for (int j=0; j<T ; j++) {
                bw.write(""+result[i][j]+ " ");
                if(j==T-1) bw.append("\n");
            }
        }

        bw.close();
    }

    private static void search (int start, int end, int init) {
        if(start==end && visitedStack) {
            result[init][end] = 1;
            return;
        }

        for(int i = 0; i < T ; i++) {
            if(i==start) continue;
            if(matrix[start][i].equals(1) && !visited[start][i]) {
                visited[start][i] = true;
                visitedStack= true;
                search(i, end, init);
            }
        }
    }
}

 

2. 그래프 탐색 (3중 반복문) [ 백준 성공 ]

public class no11403 {
    static int T;
    static String[][] matrix;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 맵 구성
        T = Integer.parseInt(br.readLine());
        matrix= new String[T][T];
        for(int i=0; i<T ; i++) {
            matrix[i] = br.readLine().split(" ");
        }

        for(int y=0; y<T ; y++) {
            for(int x=0; x<T ;x++) {
                for (int z=0; z<T ; z++) {
                    if(matrix[x][y].equals("1") && matrix[y][z].equals("1")) {
                        matrix[x][z] = "1";
                    }
                }
            }
        }

        for (int i=0; i<T ; i++) {
            for (int j=0; j<T ; j++) {
                bw.write(""+matrix[i][j]+ " ");
                if(j==T-1) bw.append("\n");
            }
        }

        bw.close();
    }
}

---

레퍼런스 코드

참고 링크 : https://settembre.tistory.com/306