[Java] 백준 1189 컴백홈 - 실버2

 

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

1189번: 컴백홈

 

 가장 먼저 떠오른 방법은 갈 수 있는 길 중 k개를 선택하는 것이었다. 하지만 해당 선택한 길이 이어지는지도 체크해야하는 번거로움이 있었기 때문에 다른 방법을 사용하기로 하였다.

 선택한 방법은 백트래킹이고, 가지치기 조건은 다음과 같다. 

1. k보다 커지면 가지치기
2. T를 지나는 경우 가지치기

 

dfs로 visit배열을 채워가면서 백트래킹하는 방식으로 구현하였다.

 

 

백트래킹 풀이(내 풀이)

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

public class Main {
  static boolean[][] canVisit;
  static int K;
  static int result = 0;

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

    int rowLen = Integer.parseInt(st.nextToken());
    int colLen = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    canVisit = new boolean[rowLen][colLen];

    for (int i =0; i<rowLen; i++) {
      String tmp = br.readLine();
      for (int j =0; j<colLen; j++) {
        if (tmp.charAt(j) == '.')
          canVisit[i][j] = true;
      }
    }

    canVisit[rowLen-1][0] = false;
    dfs(rowLen-1, 0, 1);

    System.out.println(result);
  }

  static void dfs(int row, int col, int sum) {
    if (sum == K) {
      if (col == canVisit[0].length-1 && row == 0)
        result++;

      return;
    }

    if (row-1 >= 0 && canVisit[row-1][col]) {
      canVisit[row-1][col] = false;
      dfs(row-1, col, sum+1);
      canVisit[row-1][col] = true;
    }

    if (row+1 < canVisit.length && canVisit[row+1][col]) {
      canVisit[row+1][col] = false;
      dfs(row+1, col, sum+1);
      canVisit[row+1][col] = true;
    }

    if (col-1 >= 0 && canVisit[row][col-1]) {
      canVisit[row][col-1] = false;
      dfs(row, col-1, sum+1);
      canVisit[row][col-1] = true;
    }

    if (col+1 < canVisit[0].length && canVisit[row][col+1]) {
      canVisit[row][col+1] = false;
      dfs(row, col+1, sum+1);
      canVisit[row][col+1] = true;
    }
  }
}

• (if문이 많아서 좀 더럽다)
• canVisit 부분을 만들어 방문 가능한 점인지 체크하였다
  • T 부분일 경우, 이미 방문한 경우 canVisit=false로 설정하였다
• dfs로 깊이우선 탐색을 하였다
  • 첫 시작점은 (row-1, 0)(왼쪽 아래) 이고 sum은 1로 시작한다 - 문제 정의가 1을 더해야 풀림
  • sum이 K와 같아졌을 때 끝점(오른쪽 위)이면 result 를 1 더해준다
  • sum이 K와 같아졌을 때 끝점이 아니면 그냥 return해준다 (더 계산해봤자 K보다 커짐)
  • 상, 하, 좌, 우 4가지 경우 모두 체크해준다

 

 

if 문이 너무 많은 게 보기 싫어 다른 풀이도 찾아봤다

if문을 줄이기 위해서 moveRow, moveCol 배열을 만들어 [-1, 1, 0, 0] 이런식으로 지정 후 for문을 사용하면 조금 코드를 줄일 수 있었다.

 

 

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

public class Solution {
  static boolean[][] canVisit;
  static int K;
  static int result = 0;

  static int[] moveRow = {1, -1, 0, 0};
  static int[] moveCol = {0, 0, 1, -1};

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

    int rowLen = Integer.parseInt(st.nextToken());
    int colLen = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    canVisit = new boolean[rowLen][colLen];

    for (int i =0; i<rowLen; i++) {
      String tmp = br.readLine();
      for (int j =0; j<colLen; j++) {
        if (tmp.charAt(j) == '.')
          canVisit[i][j] = true;
      }
    }

    canVisit[rowLen-1][0] = false;
    dfs(rowLen-1, 0, 1);

    System.out.println(result);
  }

  static void dfs(int row, int col, int sum) {
    if (sum == K) {
      if (col == canVisit[0].length-1 && row == 0)
        result++;

      return;
    }

    for (int i =0; i<4; i++) {
      int nextR = row + moveRow[i];
      int nextC = col + moveCol[i];

      if (0 <= nextR && nextR < canVisit.length && 0 <= nextC && nextC < canVisit[0].length) {
        if (canVisit[nextR][nextC]) {
          canVisit[nextR][nextC] = false;
          dfs(nextR, nextC, sum+1);
          canVisit[nextR][nextC] = true;
        }
      }
    }
  }
}

가독성도 훨씬 좋고 실수할 위험도 줄어들어서 이렇게 하는 게 가장 좋은 방법 같다.