[백준] 9205 맥주 마시면서 걸어가기 / 자바(Java)

문제

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

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

 

---

해설

기초적인 BFS문제입니다.

편의점의 좌표만이 나와있기 때문에 어느 편의점을 방문했는가 여부를 알기위해 입력값을 받을 때 편의점별로 추가로 인덱스를 저장하여 줍니다.

---

코드

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{

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			int N = Integer.parseInt(br.readLine());
			
			int [][] point = new int [N+2][3];
			for(int i=0;i<N+2;i++) {
				st = new StringTokenizer(br.readLine());
				point[i][0] = Integer.parseInt(st.nextToken());
				point[i][1] = Integer.parseInt(st.nextToken());
				point[i][2]=i;
			}
			String ans="sad";
			Queue<int[]> q = new LinkedList<>();
			boolean visit[] = new boolean [N+2];
			q.offer(point[0]);
			visit[0]=true;
			while(!q.isEmpty()) {
				int [] cur = q.poll();
				int r = cur[0];
				int c = cur[1];
				if(cur[2]==N+1) {
					ans="happy";
					break;
				}

				for(int i=1;i<N+2;i++) {
					if(!visit[point[i][2]]&&distance(cur,point[i])) {
						q.offer(point[i]);
						visit[point[i][2]]=true;
					}
				}

			}
			System.out.println(ans);
		}
	}

	private static boolean distance(int[] cur, int[] target) {
		if(Math.abs(cur[0]-target[0])+Math.abs(cur[1]-target[1])<=1000)return true;
		return false;
	}
}