백준 9205번 : 맥주 마시면서 걸어가기

 문제

www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

9205 맥주 마시면서 걸어가기

 

 구현 방법

 플로이드-와샬 알고리즘으로 풀 수도 있지만 너무 어려워,,서 bfs로 풀어주었습니다.

 

처음 시작은 상근이의 집이므로 큐에는 상근이의 집 좌표를 저장, 이동하는 곳으로는 편의점과 락 페스티벌로 입력받은 좌표를 List에 저장하였습니다. 다음 bfs를 돌려 현재 좌표에서 다음 갈 곳의 좌표간의 거리를 구해준 다음 방문을 하지 않았고 맥주가 남아있을 경우에만 큐에 추가해주었습니다. 맥주가 다 떨어지면 방문을 하지 않고 그러다 락 페스티벌에 도착하지 못한 채 모든 방문이 끝나면 sad, 모든 방문이 끝나기 전에 락 페스티벌 좌표에 도착하면 happy를 출력해주었습니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ9205_맥주마시면서걸어가기 {
	static boolean[] visited;
	static List<int[]> list;
	static Queue<int[]> queue;
	static boolean flag;
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc=0;tc<TC;tc++) {
			N = Integer.parseInt(br.readLine());
			visited = new boolean[N+1];
			queue = new LinkedList<>();
			list = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			int houseX = Integer.parseInt(st.nextToken());
			int houseY = Integer.parseInt(st.nextToken());
			queue.offer(new int[] {houseX, houseY});
			for (int i=0;i<N+1;i++) {
				st = new StringTokenizer(br.readLine());
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				list.add(new int[] {r, c});
			}
			flag = false;
			bfs();
			if (flag) sb.append("happy\n");
			if (!flag) sb.append("sad\n");
		}
		System.out.println(sb);
	}
	
	static void bfs() {
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
            // 페스티벌에 도착하면 끝
			if (now[0]==list.get(list.size()-1)[0] && now[1] == list.get(list.size()-1)[1]) {
				flag = true;
				break;
			}
			for (int i=0;i<N+1;i++) {
				if (!visited[i]) {
					double dis = distance(now[0], now[1], list.get(i)[0], list.get(i)[1]);
					if (dis<=1000) { // 맥주가 남아있다!!
						queue.offer(new int[] {list.get(i)[0], list.get(i)[1]});
						visited[i] = true;
					}
				}
			}
		}
	}
	
	static double distance(int startX, int endX, int startY, int endY) {
		return Math.abs(startY-startX)+Math.abs(endY-endX);
	}
}

 

정답!