[BOJ] 9205 맥주 마시면서 걸어가기

9205번: 맥주 마시면서 걸어가기 (acmicpc.net)

풀이 아이디어

오늘 공부한 플로이드-워셜 알고리즘을 사용해서 풀었다.
물론 다른 방법들도 있을 것 같다.

  1. 입력을 받아 2차원 정수 배열에 저장한다.
  2. 맥주 20잔과 1잔당 50m 이기 때문에 한번에 최대 이동가능한 거리는 1000 이다.
  3. 맨하튼 거리를 측정해서 boolean 2차원 행렬로 변환한다.
  4. 이때 거리를 계산해서 거리가 1000이하이면 그래프에 연결 여부를 true로 표시한다.
  5. 플로이드-워셜 알고리즘을 사용해서 from – to를 계산한다.
  6. from-via와 via-to 가 true인 경우 from-to, to-from = true 가 된다.
  7. 모든 정점에 대한 계산을 마친 후 집에서 공연장까지 연결되어있는 지 확인한다.
    [from][to] 가 true 이면 연결된 것이기 때문에 집이 들어있는 0 인덱스와
    공연장이 들어있는 N+1 번째 인덱스를 넣어주면 된다.
  8. if( result[0][N+1] ) -> print happy
  9. 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);
	}

}