[백준/11403] 경로 찾기 (Java)

Question

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

• 분류 : 그래프 탐색

• 풀이 시간 : 10분

문제 해설

1. 가중치 없는 방향 그래프 G가 주어졌을 때
2. 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하시오

Solution

풀이 접근 방법

1. 모든 정점에 대하여 경로 확인 = 플로이드-와샬 알고리즘 사용

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  static int N;
  static int INF = 987654321;

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

    N = Integer.valueOf(br.readLine());
    int[][] map = new int[N][N];

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());

      for (int j = 0; j < N; j++) {
        // 이동할 수 있는 경로가 있으면 1로 초기화
        // 이동 경로 없으면 INF 로 초기화
        if (st.nextToken().equals("1"))
          map[i][j] = 1;
        else
          map[i][j] = INF;
      }
    }

    // 모든 node에 대하여 서로 이어져있는지, 경로 최소값 구하기
    floydWarshall(map);
    
    int value = 0;

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        // 경로가 초기화된 상태 그대로가 아니면 = 갈 수 있다는 뜻 = 1
        value = map[i][j] != INF ? 1 : 0;
        answer.append(value + " ");
      }
      answer.append("\n");
    }

    bw.write(answer.toString() + "\n");
    bw.flush();
    bw.close();
  }

  static void floydWarshall(int[][] map) {
    // 모든 정점에 대하여 경유지 k를 거치지 않고 갈 때와
    // 경유지를 거쳐서 갈 때 중 더 작은 비용이 드는 경로 선택
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
        }
      }
    }
  }

}

알.쓸.유.메(알아두면 쓸데있는 유용한 메소드)

Pattern 클래스

java.util.regex.Pattern

• matches(String regex, String input)
  • String regex : 정규 표현식
  • String input : 검증 대상 문자열
  • 정규 표현식에 대상 문자열을 검증
  • 일치하면 true, 불일치하면 flase
• compile(String regex)
  • 주어진 정규표현식으로부터 패턴 생성
• pattern()
  • 컴파일된 정규표현식을 String 형태로 반환