[백준] 16174 점프왕쩰리(Large)

1. 문제

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

16174번: 점프왕 쩰리 (Large)

2. 접근방법

단순한 그래프 완탐문제

 

0,0 에서 출발해서 점프숫자만큼 점프하며 N-1,N-1 에 도착하면 끝나는 문제다

심지어 도착 점에는 점프 값으로 -1을 주니 정말 단순한 문제

bfs나 dfs 어떤 것을 사용해도 상관없다.

 

나는 dfs를 사용하여 풀이하였다.

0,0에서 시작해서 점프의 크기만큼 상하좌우를 탐색해서 갈 수 있는 방향으로 가고

또 도착한 곳에서 갈 수 있는 곳으로 가보고 반복하다 -1을 만나면 HaruHaru 출력 후 종료

갈 수 있는 모든 길을 가봤는데 가지 못했다면 Hing 출력 후 종료 하면 된다.

참고로

이미 방문한 곳은 굳이 다시 갈 필요가 없으니 dfs에서 빠져나왔다고 visit을 false로 해 줄 필요가 없다.

3. 풀이

1. 맵 입력 받고 바로 0,0부터 dfs 시작

2. 현재 좌표의 jump값을 확인하고 jump만큼 상하좌우 탐색

3. 갈 수 있는 길이 있으면 jump하고 visit처리

4. 도착한 곳의 jump 값이 -1이면 HaruHaru 출력하고 프로그램 종료

5. dfs를 모두 돌고 나왔으면 Hing 출력

 

4. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P16174점프왕쩰리 {

	static int map[][];
	static int dr[] = { 1, 0 };
	static int dc[] = { 0, 1 };
	static int N;
	static boolean visit[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(new Point(0, 0));
		System.out.println("Hing");
	}

	static void dfs(Point p) {
		int jump = map[p.x][p.y];
		if (jump == -1) {
			System.out.println("HaruHaru");
			System.exit(0);
		}

		for (int i = 0; i < 2; i++) {
			int row = p.x + dr[i] * jump;
			int col = p.y + dc[i] * jump;

			if (row < 0 || col < 0 || row >= N || col >= N)
				continue;
			if (visit[row][col])
				continue;

			visit[row][col] = true;
			dfs(new Point(row, col));
		}

	}

}

5. 마치며

어렵지 않았던 문제

만약 메모리 초과가 나온다면 dfs에서 빠져 나올때 visit을 false해줬는지 확인해보자