[Python] 백준 16173번 16174번 문제, 점프왕 쩰리 시리즈

<문제 링크>

 

https://www.acmicpc.net/problem/16173

16173번: 점프왕 쩰리 (Small)

https://www.acmicpc.net/problem/16174

 

---

<풀이>

 

이 문제는 주어진 맵 밖을 벗어나거나 -1(맨 우측 하단)에 도달하지 못하면 게임에 져서 "Hing"을 출력하고 -1에 도달하면 게임에서 승리해 "HaruHaru"를 출력한다.

세부 조건으로 시작 좌표는 맨 좌측 상단인 (0, 0)이고 움직이는 방향은 우측 또는 하단이지만, 움직일 수 있는 거리는 현재 내가 있는 칸의 숫자이다.

이런 그래프 탐색 문제는 한 번에 목적지를 찾아 내는 BFS를 애용한다.

단순한 문제라고 생각해 메모리 초과나 시간 복잡도는 생각하지 않고 기본적인 BFS만 수행했더니 문제를 쉽게 해결할 수 있었다.

움직이는 방향이 우측 또는 하단이기 미래의 우측 또는 하단의 칸 위치를 구해 맵을 벗어나면 탐색 큐에 넣지 않고 맵을 벗어나지 않는다면 탐색 큐에 넣어 BFS를 수행했다.

 

---

<코드>

board[][]: 맵

visited[][]: 방문 여부 리스트

succcess: 게임 승리 여부 판단하는 트리거

focus: 현재 있는 칸

bottom, right: 미래의 하단 칸의 좌표와 미래의 우측 칸의 좌표

---

package graph;

import java.util.*;

public class B16174 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] board = new int[N][N];
        boolean[][] visited = new boolean[N][N];

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                board[i][j] = sc.nextInt();
                visited[i][j] = false;
            }
        }

        bfs(board, visited);

        sc.close();
    }

    static void bfs(int[][] board, boolean[][] visited){
        int len = board.length;
        boolean success = false;
        Queue<int[]> que = new LinkedList<>(); // 큐
        que.add(new int[] {0, 0}); // 시작 정점 추가

        while (!que.isEmpty()) {
            int[] focus = que.poll();
            int r = focus[0], c = focus[1];
            visited[r][c] = true;

            if(board[r][c] == -1){
                success = true;
                break;
            }

            int bottom = r + board[r][c], right = c + board[r][c];

            if (bottom < len && !visited[bottom][c]){
                que.add(new int[] {r + board[r][c], c});
                visited[bottom][c] = true;
            }
            if (right < len && !visited[r][right]){
                que.add(new int[] {r, c + board[r][c]});
                visited[r][right] = true;
            }
        }

        if(success){
            System.out.println("HaruHaru");
        }else{
            System.out.println("Hing");
        }
    }
}