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

-Code

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

public class BOJ9250 {
    static class Pos {
        int row, col;

        public Pos (String line) {
            StringTokenizer st = new StringTokenizer(line);
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            this.row = row;
            this.col = col;
        }
    }
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = 
                new BufferedReader(new InputStreamReader(System.in));
        
        int testCase = Integer.parseInt(br.readLine());

        for (int test = 0; test < testCase; test++) {
            int storeCnt = Integer.parseInt(br.readLine());
            visited = new boolean[storeCnt + 2];
            Pos[] map = new Pos[storeCnt + 2];
            // 시작은 집 마지막이 페스티벌
            for (int i = 0; i < storeCnt + 2; i++) {
                map[i] = new Pos(br.readLine());
            }

            System.out.println(isFestivalJoin(map));
        }
    }

    private static String isFestivalJoin(Pos[] map) {
        // 집과 페스티벌 위치 셋팅
        Pos home = map[0];
        Pos festival = map[map.length - 1];
        // 방문 처리와 덱 셋팅
        visited[0] = true;
        Deque<Pos> posDeq = new ArrayDeque<>();
        posDeq.addLast(home);

        while (!posDeq.isEmpty()) {
            Pos now = posDeq.pollFirst();
            // 도착이면 happy
            if (now.row == festival.row && now.col == festival.col) {
                return "happy";
            }
            // 맵 전체 탐색
            for (int i = 1; i < map.length; i++) {
                Pos next = map[i];
                // 거리가 1000이하이고 방문하지 않은 경우 탐색
                if (isMove(now, next) && !visited[i]) {
                    visited[i] = true;
                    posDeq.addLast(next);
                }
            }
        }
        return "sad";
    }
    // 이동 가능한지 확인
    private static boolean isMove(Pos now, Pos next) {
        return (Math.abs(now.row - next.row) + Math.abs(now.col - next.col)) <= 1000;
    }
}

다른 BFS 문제와 다르게 응용이 좀 들어가야 풀 수 있는 문제여서 힌트를 찾아 해결을 했습니다. 원래 dRow, dCol로 상하좌우 혹은 더 여러 개의 이동이 정해져 있어서 그를 통해 탐색하듯 풀어야 하나 했지만 다른 접근이었습니다.

1. 거리가 1000이하이므로 해당 계산식을 가지고 이하면 탐색하는 식으로 해야 한다.
2. dRow, dCol이 아니라 일차원 배열로 index를 기준으로 모든 map을 다 돌면 된다.

위의 2개의 힌트를 보고 class를 만들어서 row, col을 저장하고 이동 가능한 위치를 담아 모든 위치를 탐색하여 페스티벌 위치에 도착하게 되면 happy 아니면 sad를 반환하도록 하여 해결했습니다.