백준[16173] - 점프왕 쩰리 (Small)

• 문제: https://www.acmicpc.net/problem/16173
• 분류: 그래프 이론, BFS, DFS, 브루트포스
• 난이도: S4
• 소요시간: 10m
• 자아성찰:
  • 맵의 크기가 N x N (N <= 3) 으로 매우매우 작으므로, BFS와 DFS 어떤 방식을 사용해도 풀 수 있다.
  • BFS를 사용하든, DFS를 사용하든 가장 중요한 포인트는 이동할 수 있는 모든 경우의 수를 따져보는 것이다.
  • 최단거리를 구하는 것이 아닌, 성공 여부만을 묻는 것이므로 DFS도 가능!
  • 이번 문제는 BFS를 통해 풀어보았다.
  • 메모리를 조금이라도 아껴보려고 기존 map에 특정 상수를 넣어 방문여부를 체크했는데, 그냥 visited 배열을 두는 것이 코드 상 더 깔끔해 보일 수도 있었겠다.

16173번: 점프왕 쩰리 (Small)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_16173 {

    static String result = "Hing";
    static int[][] map;
    static int N;
    static final int VISITED = -2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        bfs();
        System.out.println(result);
    }

    public static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        // 최초 위치에서 시작 (1, 1)
        queue.add(new Node(1, 1));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            // 현재 위치가 -1이라면 도달 가능이므로 종료
            if (map[cur.x][cur.y] == -1) {
                result = "HaruHaru";
                return;
            }
            // 방문했음을 표시하기 위헤 map 데이터 덮어씌워지므로 데이터 미리 꺼내둠
            int num = map[cur.x][cur.y];
            // 현재위치 방문 표시
            map[cur.x][cur.y] = VISITED;
            // 맵을 넘어가지 않고, 방문하지 않은 경우 Queue에 저장 (왼쪽, 아래쪽 각각 이동)
            if (cur.x + num <= N && map[cur.x + num][cur.y] != VISITED) {
                queue.add(new Node(cur.x + num, cur.y));
            }
            if (cur.y + num <= N && map[cur.x][cur.y + num] != VISITED) {
                queue.add(new Node(cur.x, cur.y + num));
            }
        }
    }

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}