백준 문제 풀이(1189번) java

문제

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

풀이

이 문제는 DFS 방법으로 풀어야한다. 출발 지점이 왼쪽 하단이고 도착 지점이 오른쪽 상단이므로 입력값으로 받는 R, C로 시작점을 (R-1, 0) 도착점을 (0, C-1)로 하여 문제를 풀었다. 모든 배열의 값은 시작점을 제외하고 0으로 시작하고 시작점은 1로 시작하게 하고 해당 위치를 지나가면 그 배열의 인덱스 값을 1로 바꿔준다. DFS를 사용하므로 한 쪽 방향으로 시작하여 입력값으로 T를 받는 배열의 위치를 제외하고 모든 값이 채워질 때까지 재귀적으로 호출한다. 재귀 호출이 끝나면 마지막으로 채워진 배열 위치의 인덱스 값을 0으로 바꿔준다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_1189 {

    static int R, C, K;
    static int[][] map;
    static int[][] visit;

    static int[] Rmove = {1, -1, 0, 0}; // 아래, 위, 오른쪽, 왼쪽 순으로 진행
    static int[] Cmove = {0, 0, 1, -1};
    static int count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int [R][C];
        visit = new int[R][C];

        for (int i = 0; i < R; i++) {

            String s = br.readLine();
            for (int j = 0; j < C; j++) {

                map[i][j] = s.charAt(j);
            }
        }

        visit[R - 1][0] = 1; // 시작지점을 1로 초기화시킴
        moving(R - 1, 0, 1);
        System.out.println(count);

    }

    static void moving(int r, int c, int k) {

        if (k == K) {
            if (r == 0 && c == C - 1) {
                count++;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {

            int Rlocate = r + Rmove[i];
            int Clocate = c + Cmove[i];
            if (Rlocate < 0 || Rlocate >= R || Clocate < 0 || Clocate >= C) {
                continue;
            }
            if (visit[Rlocate][Clocate] == 1 || map[Rlocate][Clocate] == 'T') {
                continue;
            }
            visit[Rlocate][Clocate] = 1;
            moving(Rlocate, Clocate,k+1);
            visit[Rlocate][Clocate] = 0; // 모든 인덱스의 값이 1이 되었거나, k값이 K와 같으면 이 코드가 실행됨
        }
    }
}

응용

문제가 최소거리를 구하는 거라면 Rmove와 Cmove에서 아래와 왼쪽은 사용하지 않아도 됨.