[백준 17070] 파이프 옮기기 1 (C#, C++) - soo:bak

문제 링크

17070번 - 파이프 옮기기 1

설명

파이프는 두 칸을 차지하며 가로, 세로, 대각선 세 가지 방향이 있습니다. 파이프를 밀어서 한쪽 끝을 (N, N)까지 이동시키는 방법의 수를 구하는 문제입니다.

접근법

파이프의 현재 방향에 따라 이동할 수 있는 방향이 제한됩니다. 가로 상태에서는 가로나 대각선으로만 이동할 수 있고, 세로 상태에서는 세로나 대각선으로만 이동할 수 있습니다. 대각선 상태에서는 세 방향 모두 이동할 수 있습니다.

대각선으로 이동할 때는 오른쪽, 아래쪽, 대각선 아래 세 칸이 모두 비어 있어야 합니다. 가로나 세로 이동은 이동하려는 칸만 비어 있으면 됩니다.

N이 최대 16이고 경우의 수가 100만 미만이므로, DFS로 모든 경로를 탐색하며 목표 지점에 도달할 때마다 경우의 수를 증가시키면 됩니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int N;
    static int[,] board = new int[16, 16];
    static int ans = 0;
    static readonly int[] dr = { 0, 1, 1 };
    static readonly int[] dc = { 1, 0, 1 };

    static void Dfs(int r, int c, int dir) {
      if (r == N - 1 && c == N - 1) {
        ans++;
        return;
      }

      if (dir != 1) {
        var nr = r + dr[0];
        var nc = c + dc[0];
        if (nc < N && board[r, nc] == 0)
          Dfs(nr, nc, 0);
      }

      if (dir != 0) {
        var nr = r + dr[1];
        var nc = c + dc[1];
        if (nr < N && board[nr, c] == 0)
          Dfs(nr, nc, 1);
      }

      var drd = r + dr[2];
      var dcd = c + dc[2];
      if (drd < N && dcd < N &&
          board[r, dcd] == 0 && board[drd, c] == 0 && board[drd, dcd] == 0) {
        Dfs(drd, dcd, 2);
      }
    }

    static void Main(string[] args) {
      N = int.Parse(Console.ReadLine()!);
      for (var i = 0; i < N; i++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        for (var j = 0; j < N; j++)
          board[i, j] = line[j];
      }
      Dfs(0, 1, 0);
      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int N, ans = 0;
int board[16][16];
int dr[3] = {0, 1, 1};
int dc[3] = {1, 0, 1};

void dfs(int r, int c, int dir) {
  if (r == N - 1 && c == N - 1) {
    ans++;
    return;
  }

  if (dir != 1) {
    int nr = r + dr[0];
    int nc = c + dc[0];
    if (nc < N && board[r][nc] == 0)
      dfs(nr, nc, 0);
  }

  if (dir != 0) {
    int nr = r + dr[1];
    int nc = c + dc[1];
    if (nr < N && board[nr][c] == 0)
      dfs(nr, nc, 1);
  }

  int nr = r + dr[2];
  int nc = c + dc[2];
  if (nr < N && nc < N &&
      board[r][nc] == 0 && board[nr][c] == 0 && board[nr][nc] == 0) {
    dfs(nr, nc, 2);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++)
      cin >> board[i][j];
  }

  dfs(0, 1, 0);
  cout << ans << "\n";

  return 0;
}