알고리즘/완전탐색(BFS,DFS)
BOJ - 9205 ) 맥주 마시면서 걸어가기
개발자가될수있을까?
2020. 11. 26. 21:24
9205번: 맥주 마시면서 걸어가기
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.
www.acmicpc.net
각 정점에서 최대거리 ( x + y = 1000칸 움직임 ) 에 편의점이있거나 현재 정점에서
페스티벌위치까지 갈수있는지 판단하기 위해서 재귀함수를 이용하여 매 정점을 체크해준다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n,ex,ey;
public static int cov[][];
public static boolean visit[];
public static String answer ="sad";
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(st.nextToken());
for(int i = 0 ; i < t ; i++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int sx = Integer.parseInt(st.nextToken());
int sy = Integer.parseInt(st.nextToken());
cov = new int[n][2];
visit = new boolean[n];
for(int j= 0; j < n ; j++) {
st = new StringTokenizer(br.readLine());
cov[j][0] = Integer.parseInt(st.nextToken());
cov[j][1] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
ex = Integer.parseInt(st.nextToken());
ey = Integer.parseInt(st.nextToken());
DFS(sx,sy);
sb.append(answer+"\n");
answer ="sad";
}
System.out.print(sb);
}
private static void DFS(int sx, int sy) {
if(dist(sx,ex,sy,ey)) {
answer ="happy";
return ;
}
for(int i=0 ; i < n ; i ++) {
int nx = cov[i][0];
int ny = cov[i][1];
if(dist(sx,nx,sy,ny) && !visit[i]) {
visit[i] = true;
DFS(nx,ny);
}
}
}
private static boolean dist(int sx, int ex2, int sy, int ey2) {
return ( Math.abs(ex2-sx) + Math.abs(ey2-sy) ) <= 1000 ;
}
}
