맨 처음 받는 숫자만큼 테스트를 실행하니
for문으로 bfs를 돌려준다.
시작위치와 도착위치를 각각 (sRow,sCol) (fRow, fCol) 로 지정하고
bfs의 while문에서 시작위치와 도착위치가 같아지면 while문을 끝내고 happy 저장
맥주를 마시고 거리 1000을 갈 수 있으니 두 Row값의 차와 Col값의 차가 1000을 넘기면 countinue로 건너뛰기
bfs의 while문 맨 처음에 시작위치와 끝 위치의 차이가 1000을 넘기지 않는다면
바로 happy를 저장하고 while문을 끝내도 좋을 것 같다.
import java.util.*;
public class B9205 {
static int t, n;
static int[][] Board;
static boolean[] visited;
static ArrayList<String> res = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int i=0; i<t; i++){
n = sc.nextInt();
Board = new int[n+2][2];
visited = new boolean[n+2];
for(int j=0; j<n+2; j++){
Board[j][0] = sc.nextInt();
Board[j][1] = sc.nextInt();
}
int sRow = Board[0][0];
int sCol = Board[0][1];
int fRow = Board[n+1][0];
int fCol = Board[n+1][1];
bfs(sRow , sCol, fRow ,fCol);
}
for(String r : res){
System.out.println(r);
}
}
private static void bfs(int sRow, int sCol, int fRow, int fCol) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(sRow, sCol));
visited[0] = true;
boolean finish = false;
while(!queue.isEmpty()){
Node temp = queue.remove();
if(temp.r == fRow && temp.c == fCol){
finish = true;
break;
}
for(int i = 0; i<n+2; i++){
if(Math.abs(temp.r - Board[i][0]) + Math.abs(temp.c - Board[i][1]) > 1000) continue;
if(visited[i]) continue;
visited[i] = true;
queue.add(new Node(Board[i][0] , Board[i][1]));
}
}
if(finish) {
res.add("happy");
}else{
res.add("sad");
}
}
static class Node{
int r,c;
Node(int row, int col){
r = row;
c = col;
}
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 2644-촌수계산 (0) | 2022.08.13 |
---|---|
[백준 java] 2606-바이러스 (0) | 2022.08.13 |
1697-숨바꼭질 (0) | 2022.08.11 |
2573-빙산 (0) | 2022.08.10 |
5014-스타트링크 (0) | 2022.08.10 |