문제#
- 링크로 대체
풀이 및 주저리..
백준 문제중 좀 어려운 편에 속하는(정답률 30%) 문제를 이번 주 마지막 알고리즘 문제로 선택하여 풀어보았다. 얼핏 문제를 보면 좀 쉬워보이지만 꽤 고려해야할게 많은 문제이다. 가장 큰 핵심으로는 미로를 탈출하지 못하는 경우를 어떻게 코드로 구현하냐? 였던 것 같다. 이걸 해결하기 위해서는 미로 특성상 어느 위치로 가게 되면 결국 가게 되는 방향은 일정하다는 규칙을 파악하는 것이였던 것 같다. 나같은 경우는 이걸 파악은 쉽게했지만.. 코드 구현에서 큰 문제가 있었다. 처음에 내가 했던 생각을 글로 적어본다면,
- 미로 시작점(탈출가능? 불가능? 처음 도달) 을 나누어 진행
- 미로 방향대로 진행하면서 지나가고 있는 곳을 저장
- 미로 밖으로 탈출하는지 지나간 곳으로 들어왔는지 검사
- 탈출하였다면, 그동안 지나갔던 위치를 탈출할 수 있는 상태로 저장, 실패했다면 탈출불가로 저장
이런 흐름이였는데 코드로 어떻게 구현을 하냐에 도달하지 못하고 결국 답을 조금 참고하고 말았다. 내가 구현하지 못했던 부분은 재귀적으로 반환값이 있는 형태를 생각하지 못한 것이였다. DFS를 진행하면서 마지막의 값을 반환해주면서 그전의 값도 동일하게 처리하는 부분의 코드를 생각하지 못했던 것이다. 이해하는데 꽤 오랜시간이 걸렸지만... 얻어가는게 많았던 문제였다.
코드
package baekjoon.algorithm.day04;
import java.util.Arrays;
import java.util.Scanner;
public class EscapeMaze {
static final int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int N, M;
static int[][] moveMap;
static char[][] map;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int answer = 0;
N = s.nextInt();
M = s.nextInt();
s.nextLine();
map = new char[N][M];
moveMap = new int[N][M];
for (int i = 0; i < N; i++) {
map[i] = s.nextLine().toCharArray();
Arrays.fill(moveMap[i], -1);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
go(i, j);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (moveMap[i][j] == 1) answer++;
}
}
System.out.println(answer);
}
public static int changeCharDirToInt(char dir) {
if (dir == 'U') return 0;
else if (dir == 'R') return 1;
else if (dir == 'D') return 2;
else return 3;
}
public static int go(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= M) return 1;
if (moveMap[x][y] != -1) return moveMap[x][y];
moveMap[x][y] = 0;
int dir = changeCharDirToInt(map[x][y]);
moveMap[x][y] = go(x + dx[dir], y + dy[dir]);
return moveMap[x][y];
}
}기억에 남길 것!
- 재귀 함수에서의 반환값 사용