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

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

 

맨 처음 받는 숫자만큼 테스트를 실행하니 

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;
        }
    }
}