16173 점프와 쩰리

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

16173번: 점프왕 쩰리 (Small)

[난이도]

- Silver 4

 

[알고리즘]

- bfs

 

[코드]

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

public class Main {
    static int N;
    static int[] dx = {1, 0}; // 아래, 오른쪽
    static int[] dy = {0, 1}; // 아래, 오른쪽
    static int[][] graph;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        bfs();

    }
    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            if (graph[x][y] == -1) {
                System.out.println("HaruHaru");
                return;
            }
            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i] * graph[x][y];
                int ny = y + dy[i] * graph[x][y];
                if (nx < N && ny < N && !visited[nx][ny]) { // graph 범위 내라면
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        System.out.println("Hing");
    }
}

 

[풀이]

이동은 아래 혹은 오른쪽으로 밖에 이동하지 못하기 때문에 처음에는 방문한지역을 체크하는 visited 배열을 사용하지 않았었다. 하지만 게임판의 숫자는 0이상 100이하여서 0이 적혀있을 경우 제자리를 계속 방문하게 되어 메모리 초과가 발생하기 때문에 이를 해결하기위해 visited 배열을 추가했다.