백준 : 9205 (맥주마시면서 걸어가기) (BFS)

이번문제는 BFS 문제이다.

 

처음 문제를 읽었을때는 BFS문제 인가 긴가민가 했었다. 다른사람들의 풀이를 보니 플로이드와샬 알고리즘으로 푼 케이스도 있었다.

 

이번 문제가 조금 어렵게 느껴졌던 이유는 그래프 자체를 노드로 구성했다는 점,

그리고 모든 노드를 방문할 수 있다고 가정한다는 점이 새롭고 낯설게 느껴졌다.

 

비록 반례나 풀이를 조금 참고하기는 했지만, 큰 틀은 기존 BFS와 별 차이가 없음을 느낄 수 있었다.

역시 다양한 경험이 중요하다는 점을 다시한번 깨달았다.

import java.util.*;

class Node {
	private int x;
	private int y;

	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return this.x;
	}

	public int getY() {
		return this.y;
	}
}

class Main {

	static int n, m, startX, startY, finishX, finishY;
	static boolean[] visited = new boolean[m + 2]; 
	static ArrayList<Node> graph = new ArrayList<Node>();
	static String result = "sad";
	static ArrayList<String> resultArr = new ArrayList<String>();

	public static void bfs(int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(x, y));
		visited[0] = true;

		while (!q.isEmpty()) {
			Node nowNode = q.poll();
			int nowX = nowNode.getX();
			int nowY = nowNode.getY();

			if (visited[m + 1] == true) { // 락페스티벌에 도착했다면 종료*****
				result = "happy";
			}

			for (int i = 0; i < m + 2; i++) { //거리만 맞다면, 전부다 가능성 있으므로 간선이 있다고 생각한다. (양방향)*****
				Node tmp = graph.get(i);

				int dist = Math.abs(nowX - tmp.getX()) + Math.abs(nowY - tmp.getY()); // 거리계산

				if (dist <= 1000 && visited[i] == false) { // 콜라 만땅일때 갈수 있는 최대거리 (50* 20) & 아직 방문전이면*****
					q.offer(new Node(tmp.getX(), tmp.getY())); // 삽입
					visited[i] = true; // 방문표시
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); // 테스트케이스 갯수

		for (int i = 0; i < n; i++) { // 최종 갯수 = 편의점의 갯수 +2
			m = sc.nextInt(); // 편의점 갯수
			sc.nextLine(); // 버퍼

			// 초기화
			visited = new boolean[m + 2];
			graph = new ArrayList<Node>();
			result = "sad";

			for (int j = 0; j < m + 2; j++) { // 최종 갯수 = 편의점의 갯수 +2
				String st = sc.nextLine();
				String[] stArr = st.split(" ");

				int a = Integer.parseInt(stArr[0]);
				int b = Integer.parseInt(stArr[1]);

				graph.add(new Node(a, b));
				
				if(j == 0) { //시작노드 정하기*****
					startX = a;
					startY = b;
				}

				if (j == m + 1) { // 락 페스티벌 위치 정하기*****
					finishX = a;
					finishY = b;
				}
			}

			bfs(startX, startY);
			
			resultArr.add(result);
		}
		
		for(int i=0; i<resultArr.size(); i++) { //출력
			System.out.println(resultArr.get(i));
		}
	}
}