![[BOJ/Java] 16173_점프왕 쩰리 (Small) || DFS](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbzdF53%2FbtrG2uNlIp7%2FkJvIgzUfclilBgFmEeEAnk%2Fimg.png)
16173번: 점프왕 쩰리 (Small)
쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.
www.acmicpc.net
문제 설명
‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.
- ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
- ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
- ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
- ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
- ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!
입력)
입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.
입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.
출력)
‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.
예제)
❕ 문제 풀이
2차원 배열로 그래프의 연결 관계를 표현하는 방식을 이용했다.
1. 탐색할 노드를 방문 처리한다.
2. 이동 가능 거리를 계산하여 범위에 벗어나는지 확인한다. 벗어나지 않는다면 탐색
+ 이미 방문했는지, 값이 -1로 승리 지점에 해당하는지를 확인한다.
입력
static boolean check = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
boolean[][] visited = new boolean[n][n]; // 모두 false로 초기화됨
// n만큼 공백을 기준으로 이동가능 거리 입력받기
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0, arr, visited);
...
}게임에서 승리했는지 확인해주기 위해 전역 변수인 check를 선언 및 초기화를 해준다.
방문 확인을 할 visited도 2차원 배열로 모두 False로 초기화해준다.
dfs함수에 인덱스를 넣어주어 접근할 수 있도록 한다.
2차원 배열로 그래프의 연결을 표현해주었다.
StringTokenizer를 이동하여 공백을 구분하여 입력받았다.
1.
// 방문한 적이 있는지 확인
if (visited[x][y]) {
return ;
}
visited[x][y] = true;
해당 노드를 방문한 적이 있는지 확인한다.
2.
// 이동가능한지 확인
if (arr[x][y] + y < arr.length) {
dfs(x, arr[x][y] + y, arr, visited);
}
if (arr[x][y] + x < arr.length) {
dfs(arr[x][y] + x, y, arr, visited);
}입력받은 이동 가능 거리를 현재의 위치의 행과 열에 더해주면서 주어진 맵에서 벗어나는지 확인한다.
벗어나지 않는다면, 해당 위치로 DFS 함수가 실행되도록 한다.
3.
// 승리 지점에 도착했는지 확인
if (arr[x][y] == -1) {
check = true;
return ;
}승리 지점인지 확인하고, 전역 변수인 check의 값을 true로 설정해주고 리턴한다.
4.
// 전역변수인 check가 true인지 확인
if (check) {
bw.write("HaruHaru");
} else {
bw.write("Hing");
}check를 통해 승리 지점에 도달했는지에 따라 출력해준다.
✅ [ CODE ]
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static boolean check = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
boolean[][] visited = new boolean[n][n]; // 모두 false로 초기화됨
// n만큼 공백을 기준으로 이동가능 거리 입력받기
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0, arr, visited);
// 전역변수인 check가 true인지 확인
if (check) {
bw.write("HaruHaru");
} else {
bw.write("Hing");
}
bw.flush();
br.close();
bw.close();
}
static void dfs(int x, int y, int[][] arr, boolean[][] visited) {
// 방문한 적이 있는지 확인
if (visited[x][y]) {
return ;
}
visited[x][y] = true;
// 승리 지점에 도착했는지 확인
if (arr[x][y] == -1) {
check = true;
return ;
}
// 이동가능한지 확인
if (arr[x][y] + y < arr.length) {
dfs(x, arr[x][y] + y, arr, visited);
}
if (arr[x][y] + x < arr.length) {
dfs(arr[x][y] + x, y, arr, visited);
}
}
}2차원 배열을 통해 각 노드의 연결을 표현하였고, 마찬가지로 2차원 배열인 visited로 방문을 확인해주었다.
범위에 벗어나지 않는다면, 재귀 함수로 좌표를 바꾸어 탐색이 진행될 수 있도록 구현하였다.
✅ [ CODE ]
dfs 함수 매개변수로 arr과 visited를 빼주고 싶어서 check처럼 전역 변수로 빼주고, 조건들도 하나로 정리를 해주었다.
속도는 더 느려짐...! 첫 번째 코드에서는 if문으로 확인해주고 재귀함수가 실행되도록 해주었는데,
이 코드에서는 일단 실행하고 if문으로 return해주기 때문인 것 같다.
import java.io.*;
import java.util.StringTokenizer;
public class Main2 {
static boolean check = false;
static int[][] arr;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
visited = new boolean[n][n]; // 모두 false로 초기화됨
// n만큼 공백을 기준으로 이동가능 거리 입력받기
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0, 0);
// 전역변수인 check가 true인지 확인
if (check) {
bw.write("HaruHaru");
} else {
bw.write("Hing");
}
bw.flush();
br.close();
bw.close();
}
static void dfs(int x, int y) {
// 이동가능한지, 방문한 적이 있는지, 승리지점인지 확인
if (x >= arr.length || y >= arr.length) {
return ;
} else if (visited[x][y]) {
return ;
} else if (arr[x][y] == -1) {
check = true;
return ;
}
visited[x][y] = true;
dfs(x, arr[x][y] + y);
dfs(arr[x][y] + x, y);
}
}그래서 그냥 다시 if문으로 묶어주었다,, 첫 번째 코드와 속도는 동일하다.
static void dfs(int x, int y) {
if (arr[x][y] == -1) {
check = true;
return ;
}
visited[x][y] = true;
// 이동가능한지 확인
if (arr[x][y] + y < arr.length) {
if (!visited[x][arr[x][y] + y]) {
dfs(x, arr[x][y] + y);
}
}
if (arr[x][y] + x < arr.length) {
if (!visited[arr[x][y] + x][y]) {
dfs(arr[x][y] + x, y);
}
}
}