[백준] S16173

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

16173번: 점프왕 쩰리 (Small)

 

# 아이디어

N이 2 또는 3이기 때문에 2*2 와 3*3의 지도가 존재한다.

따라서 2*2에서는 한 칸 단위로 오른쪽 이동 1회, 아래쪽 이동 1회가 일어나고

3*3에서는 한 칸 단위로 오른쪽 이동 2회, 아래쪽 이동 2회가 일어난다.

 

2*2에서의 모든 경우의 수: 2

3*3에서의 모든 경우의 수: 14

직접 if문을 이용해 체크해주자.

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

		int mapSize = sc.nextInt();

		int[][] map = new int[mapSize][mapSize];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		if (mapSize == 2) {
			if (map[0][0] == 1 && map[0][1] == 1 || map[0][0] == 1 && map[1][0] == 1)
				System.out.println("HaruHaru");
			else {
				System.out.println("Hing");
			}
		}
		if (mapSize == 3) {
			if (map[0][0] == 1) {
				if ((map[0][1] == 1 && map[1][1] == 1 && map[1][2] == 1)
						|| (map[1][0] == 1 && map[1][1] == 1 && map[2][1] == 1)) {
					System.out.println("HaruHaru");
					System.exit(0);
				}
				if ((map[0][1] == 2 && map[2][1] == 1) || (map[1][0] == 2 && map[1][2] == 1)
						|| (map[0][1] == 1 && map[1][1] == 1 && map[2][1] == 1)
						|| (map[1][0] == 1 && map[1][1] == 1 && map[1][2] == 1)) {
					System.out.println("HaruHaru");
					System.exit(0);
				}
				if (map[0][2] == 2 || map[2][0] == 2
						|| ((map[0][2] == 1 && map[1][2] == 1) || (map[2][0] == 1 && map[2][1] == 1))) {
					System.out.println("HaruHaru");
					System.exit(0);
				}
			}

			else if (map[0][0] == 2) {
				if (map[0][2] == 2 || map[2][0] == 2
						|| ((map[0][2] == 1 && map[1][2] == 1) || (map[2][0] == 1 && map[2][1] == 1))) {
					System.out.println("HaruHaru");
					System.exit(0);
				}
			}

			System.out.println("Hing");
		}

		sc.close();

	}

정답이긴 하지만 아무리 생각해도 이렇게 하는건 아닌거 같다...;;

 

# 블로그 참조

오른쪽과 아래쪽으로만 한 붓 그리기를 하여 출구를 찾자.

=> DFS(깊이 우선 탐색): 최대한 깊이 내려간 뒤, 더이상 내려갈 수 없는 경우 옆으로 이동

	public static void dfs(int x, int y, int[][] map, boolean[][] visited) {
		if (visited[x][y]) {
			return;
		}
		visited[x][y] = true;

		if (map[x][y] == -1) {
			System.out.println("HaruHaru");
			System.exit(0);
		}

		if (y + map[x][y] < map.length) {
			dfs(x, y + map[x][y], map, visited);
		}
		if (x + map[x][y] < map.length) {
			dfs(x + map[x][y], y, map, visited);
		}

	}

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

		int mapSize = sc.nextInt();

		int[][] map = new int[mapSize][mapSize];
		boolean[][] visited = new boolean[mapSize][mapSize];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = false;
			}
		}

		dfs(0, 0, map, visited);

		System.out.println("Hing");

		sc.close();

	}

dfs()함수는 매개변수로 x, y, map, visited를 갖고 (0,0)부터 탐색을 시작해 해당 위치의 값만큼 더한 좌표들을 재귀를 통해 다시 dfs 탐색을 한다.

 

🤔

보면 알겠는데... 과연 코딩을 할 수 있을까??? 라는 생각이 드는 정답 코드..

visited[][]배열 까지는 생각했는데 현재 좌표값에서 가중치를 좌표에 더하여 재귀 함수로 반복하는 아이디어를 떠오르지 못했다.. ㅠㅠ

 

💯💯💯

이제 Scanner를 버릴 때가 된거 같다.. 제출 시간이 점점 오래 걸리기 시작함.