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

https://www.acmicpc.net/problem/9205

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

 

 

 

 

 

그래프 탐색 문제이다. 처음에는 입력에서 주어진 좌표로 가능한 범위로 그래프를 만들어서 탐색을 돌려야 하나 생각했었다. 하지만 좌표 자체를 한 정점으로 생각하고 정점 간 탐색을 해주면 됐었다.

 

0. 입력받을 때 편의점의 좌표를 Dot이라는 객체 배열에 저장한다.

1. 상근이네 집을 시작으로 BFS 탐색을 한다.

2. 락페에 도착할 수 있는지 검사를 한다.(맨하탄 거리가 1000이하여야 한다.) 도착할 수 있으면 바로 TRUE를 리턴한다.

3. 모든 편의점에 대해 탐색을 한다.

4. 방문하지 않았고, 20병 안에 갈 수 있으면(맨하탄 거리가 1000이하이면) 큐에 넣어주고 방문체크를 해준다.

5. 큐가 빌때까지 반복한다.

6. 중간에 리턴되지 않고 끝났다면 락페에 도착 못한 것이다.

 

 

 

 

 

코드

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

public class Main {
	static int n;
	static Dot[] stores;
	static boolean[] visited;
	
	static class Dot {
		int x, y;

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

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수
		
		StringBuilder sb = new StringBuilder();
		for(int t = 0; t < T; t++) { 
			n = Integer.parseInt(br.readLine()); //편의점의 개수
			
			//상근이네 집 좌표
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int hx = Integer.parseInt(st.nextToken());
			int hy = Integer.parseInt(st.nextToken());
			
			stores = new Dot[n];
			
			//편의점 좌표
			for(int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int cx = Integer.parseInt(st.nextToken());
				int cy = Integer.parseInt(st.nextToken());
				
				//배열에 담기
				stores[i] = new Dot(cx, cy);
			}
			
			//락페 좌표
			st = new StringTokenizer(br.readLine(), " ");
			int fx = Integer.parseInt(st.nextToken());
			int fy = Integer.parseInt(st.nextToken());

			//구현
			visited = new boolean[n];
			
			if(bfs(hx, hy, fx, fy)) { //행복하게 페스티벌에 갈 수 있음
				sb.append("happy\n");
			}else {
				sb.append("sad\n");
			}
		}
		
		System.out.println(sb);
	}

	public static boolean bfs(int hx, int hy, int fx, int fy) {
		Queue<Dot> queue = new LinkedList<>();
		
		queue.add(new Dot(hx, hy)); //시작점
		
		while(!queue.isEmpty()) {
			Dot dot = queue.poll();
			
			int dist = getDistance(dot.x, dot.y, fx, fy);
			
			if(dist <= 1000) { //락페까지 도착 가능
				return true;
			}
			
			for(int i = 0; i < n; i++) { //모든 편의점에 대해 탐색
				if(!visited[i]) { //방문하지 않았고
					int nx = stores[i].x;
					int ny = stores[i].y;
					
					dist = getDistance(dot.x, dot.y, nx, ny);
					
					if(dist <= 1000) { //20병 안에 갈 수 있으면
						queue.add(new Dot(nx, ny));
						visited[i] = true;
					}
				}
			}
		}
		return false;
	}

	public static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x2 - x1) + Math.abs(y2 - y1);
	}

}

 

 

 

 

 

 

결과