9205번: 맥주 마시면서 걸어가기 (acmicpc.net)
풀이 아이디어
오늘 공부한 플로이드-워셜 알고리즘을 사용해서 풀었다.
물론 다른 방법들도 있을 것 같다.
- 입력을 받아 2차원 정수 배열에 저장한다.
- 맥주 20잔과 1잔당 50m 이기 때문에 한번에 최대 이동가능한 거리는 1000 이다.
- 맨하튼 거리를 측정해서 boolean 2차원 행렬로 변환한다.
- 이때 거리를 계산해서 거리가 1000이하이면 그래프에 연결 여부를 true로 표시한다.
- 플로이드-워셜 알고리즘을 사용해서 from – to를 계산한다.
- from-via와 via-to 가 true인 경우 from-to, to-from = true 가 된다.
- 모든 정점에 대한 계산을 마친 후 집에서 공연장까지 연결되어있는 지 확인한다.
[from][to] 가 true 이면 연결된 것이기 때문에 집이 들어있는 0 인덱스와
공연장이 들어있는 N+1 번째 인덱스를 넣어주면 된다. - if( result[0][N+1] ) -> print happy
- else -> print sad
코드
package com.algo.boj; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ9205BeerWalk { private static int[][] graph; private static boolean[][] result; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int TC = Integer.parseInt(br.readLine()); StringTokenizer st = null; for (int testCase = 0; testCase < TC; testCase++) { //testCase수 만큼반복한다. int N = Integer.parseInt(br.readLine()); //편의점의 수를 입력받는다. graph= new int[N+2][2]; // 집 + 편의점 + 공연장 => 1 + N + 1 for (int j = 0; j < N+2; j++) { st = new StringTokenizer(br.readLine()); graph[j] =new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; } result = new boolean[N+2][N+2]; //정점이 연결되어 있는지를 담는 배열 for (int j = 0; j < result.length; j++) { for (int j2 = 0; j2 < result.length; j2++) { //i,j의 맨하튼 거리가 1000보다 작은 경우 ( 연결된 경우) if(getDistance(graph[j][0], graph[j][1], graph[j2][0], graph[j2][1])<=1000) { result[j][j2] = true; result[j2][j] = true; } } } for (int via = 0; via < N+2; via++) { for (int from = 0; from < N+2; from++) { if(via==from)continue; for (int to =0; to < N+2; to++) { if(from==to || via==to)continue; //from - via와 via-to 가 연결된 경우 from-to, to-from도 연결된다. if(result[from][via] && result[via][to]) { result[from][to] =true; result[to][from] =true; } } } }//for // 0==집의 인덱스, N+1==공연장의 인덱스 if(result[0][N+1]) { //연결된 경로가 존재하는 경우 System.out.println("happy"); }else { //연결된 경로가 없는 경우 System.out.println("sad"); } }//testCase } //맨하튼 거리를 리턴하는 함수 private static int getDistance(int x1, int y1, int x2, int y2) { return Math.abs(x1-x2) + Math.abs(y1-y2); } }