OJ
[BOJ] 17070 파이프 옮기기 1 (JAVA)
P3PP4
2022. 8. 18. 22:45
https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
DP로 푸는 게 가장 빠른 것 같지만 DFS가 먼저 떠올라 DFS로 해결했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, result;
static int[][] arr;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
} /* 입력 끝 */
link(0, 1, 0);
System.out.println(result);
}
/* state : 0 가로, 1 대각, 2 세로 */
static void link(int row, int col, int state) {
if(row == N - 1 && col == N - 1) {
result++;
return;
}
int nextR = row + 1;
int nextC = col + 1;
// 가능하면 가로로 뻗음
if(nextC < N && arr[row][nextC] == 0 && (state == 0 || state == 1)) {
link(row, nextC, 0);
}
// 가능하면 대각으로 뻗음
if(nextR < N && nextC < N && arr[row][nextC] == 0 && arr[nextR][col] == 0 && arr[nextR][nextC] == 0) {
link(nextR, nextC, 1);
}
// 가능하면 세로로 뻗음
if(nextR < N && arr[nextR][col] == 0 && (state == 1 || state == 2)) {
link(nextR, col, 2);
}
}
}