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

1. 문제

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

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

 

 

 

2. 풀이과정

 

1. 출발지부터 시작, 출발지는 방문 체크

2. 편의점, 도착지 전체를 보면서, 갈 수 있는 곳 확인한다.

- x좌표의 차이 + y좌표의 차이 <= 20개*50m = 1000이면, 갈 수 있으므로 방문 체크하고 간다.

- 갈 수 있는 곳이 도착지면, 바로 종료한다.

 

*x == N+1에서 true를 반환할 때만, true를 반환해서 하나라도 true인 걸 찾으면 반환한다. false일 때 미리 반환하면, 되는 경우를 찾기 전에 끝나서 안 된다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int N, pos[][];
	static boolean v[];
	
	public static Boolean go(int x) {
		if(x==N+1) {
			return true;
		}

		for(int i=0; i<N+2; i++) {
			if(v[i]) continue;
			if(Math.abs(pos[x][0]-pos[i][0]) + Math.abs(pos[x][1]-pos[i][1]) <= 1000) {
				v[i] = true;
				if(go(i)) return true;
			}
		}
		return false;
	}

	public static void main(String[] args) throws Exception {
		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());
			pos = new int[N+2][2];
			v = new boolean[N+2];
			for(int i=0; i<N+2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				pos[i][0] = Integer.parseInt(st.nextToken());
				pos[i][1] = Integer.parseInt(st.nextToken());
			}
			v[0] = true;
			sb.append(go(0) ? "happy\n" : "sad\n");
		}
		System.out.println(sb.toString());
	}
}