[백준] 17070번 파이프 옮기기1

17070번 파이프 옮기기1

1. 이해하기

• 파이프를 N,N으로 옮기는 경우의 수를 구하는 문제이다.
• DFS를 이용하여 구할 수 있다.
• 참고로 DFS에 DP를 추가하여 구할 수도 있다. 시간을 단축시킬 수 있다.

---

2. 구현하기

• dfs(x,y,prev)

  • 현재 위치와 이 전에 어떤 방향으로 있었는지를 받는다. 이를 이용해서 파이프가 어떤 모양으로 이어질 수 있는 지를 구한다.

    static int dfs(int x, int y, int prev) {
      if(x == N-1 && y == N-1) return 1;
    
      int ret = 0;
      for(int i = 0; i < 3; i++) {
          if((prev == 0 && i == 2) || (prev == 2 && i == 0)) continue;
          int nx = x+dx[i];
          int ny = y+dy[i];
          if(!boundary(nx,ny) || map[nx][ny] == 1 || !canMove(nx,ny,i)) continue;
          ret += dfs(nx,ny,i);
      }
      return ret;
    }

• boundary(x,y)

  • 범위를 넘어가지 않는지 체크한다.

    static boolean boundary(int x, int y) {
      return x < N && y < N;
    }

• canMove(x,y,d)

  • 현재 위치가 파이프가 지어질 수 있는지 판단한다.

    static boolean canMove(int x, int y, int d) {
      if(d == 0 || d == 2)
          return map[x][y] == 0;
      if(d == 1) 
          return map[x][y] == 0 && map[x-1][y] == 0 && map[x][y-1] == 0;
      return false;
    }

---

3. 전체 코드

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

public class Main {
    static int N;
    static int[] dx = { 0, 1, 1 };
    static int[] dy = { 1, 1, 0 };
    static int[][] map;
    static int[][][] cache;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[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());
            }
        }

        System.out.println(dfs(0,1,0));
    }

    static int dfs(int x, int y, int prev) {
        if(x == N-1 && y == N-1) return 1;

        int ret = 0;
        for(int i = 0; i < 3; i++) {
            if((prev == 0 && i == 2) || (prev == 2 && i == 0)) continue;
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(!boundary(nx,ny) || map[nx][ny] == 1 || !canMove(nx,ny,i)) continue;
            ret += dfs(nx,ny,i);
        }
        return ret;
    }

    static boolean boundary(int x, int y) {
        return x < N && y < N;
    }

    static boolean canMove(int x, int y, int d) {
        if(d == 0 || d == 2)
            return map[x][y] == 0;
        if(d == 1) 
            return map[x][y] == 0 && map[x-1][y] == 0 && map[x][y-1] == 0;
        return false;
    }

    static class Point {
        int x, y, d;

        Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}

• dp를 이용한 코드

  import java.util.Scanner;
  
  public class Main {
      static int N;
      static int[] dx = { 0, 1, 1 };
      static int[] dy = { 1, 1, 0 };
      static int[][] map;
      static int[][][] cache;
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          N = sc.nextInt();
          map = new int[N][N];
          cache = new int[N][N][3];
          for (int i = 0; i < N; i++)
              for (int j = 0; j < N; j++) {
                  map[i][j] = sc.nextInt();
                  for(int k = 0; k < 3; k++)
                      cache[i][j][k] = -1;
              }
  
          System.out.println(solve(0, 0, 1));
          sc.close();
      }
  
      static int solve(int prev, int x, int y) {
          if (x >= N || y >= N || map[x][y] == 1 || !canMove(prev,x,y))
              return 0;
          if (x == N - 1 && y == N - 1)
              return 1;
          if (cache[x][y][prev] != -1)
              return cache[x][y][prev];
          cache[x][y][prev] = 0;
          for (int i = 0; i < 3; i++) {
              if ((prev == 0 && i == 2) || (prev == 2 && i == 0))
                  continue;
              cache[x][y][prev] += solve(i, x + dx[i], y + dy[i]);
          }
          return cache[x][y][prev];
      }
  
      static boolean canMove(int prev, int x, int y) {
          if (prev == 0 || prev == 2)
              return map[x][y] == 0;
          if (prev == 1)
              return map[x][y] == 0 && map[x - 1][y] == 0 && map[x][y - 1] == 0;
          return false;
      }
  }

---

4. 느낀점

• 어렵게 생각하려하지 말고 쉬운 방법부터 차례대로 시도해보자.
• 완전탐색 -> 시간이 모자랄 것 같다 -> dp 순으로 시도하자.