링크
https://www.acmicpc.net/problem/17070
문제 설명
정답률 46.289%
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
...
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력 예제
3
0 0 0
0 0 0
0 0 0출력 예제
1풀이
그래프 탐색(DFS)
이동할 수 있는 방법은 가로, 세로 그리고 대각선이므로 다음과 같이 dr, dr를 구성한다.
int[] dr = {0, 1, 1};
int[] dc = {1, 0, 1};DFS를 이용하여 탐색하는데 탐색지점이 도착지점에 도달할 때 까지 탐색한다. 탐색 방향은 3가지 이므로 3가지의 경우에 대해 반복은 진행하고 다음의 경우를 고려한다.
- 파이프가 가로일 때 -> 세로로 이동 불가
- 파이프가 세로일 때 -> 가로로 이동 불가
- 이동할 지점에 벽이 있으면 스킵
- 대각선으로 이동할 경우 이동할 지점외에도 벽이 있는지 확인
이를 구현하면 다음과 같다.
//status를 0, 1, 2으로 가로, 세로, 대각선 판단
static void dfs(int r, int c, int status) {
//도착지점에 도달한 경우
if (r == N - 1 && c == N - 1) {
count++;
return;
}
//가로, 세로, 대각선 탐색
for (int i = 0; i < 3; i++) {
//현재 상태에서 이동 불가능한 방향은 스킵
if ((status == 0 && i == 1) || (status == 1 && i == 0)) {
continue;
}
int nextR = r + dr[i];
int nextC = c + dc[i];
//범위를 벗어나거나 벽에 막힌 경우
if (nextR >= N || nextC >= N || house[nextR][nextC] == 1) {
continue;
}
//대각선 이동 시 추가 조건 확인
if (i == 2 && (house[nextR - 1][nextC] == 1 || house[nextR][nextC - 1] == 1)) {
continue;
}
//다음 칸으로 이동
dfs(nextR, nextC, i);
}
}전체 코드
//백준
public class Main {
static final int[] dr = {0, 1, 1};
static final int[] dc = {1, 0, 1};
static int[][] house;
static int N;
static int count;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
house = new int[N][N];
for (int i = 0; i < N; i++) {
house[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
dfs(0, 1, 0);
System.out.println(count);
}
//status를 0, 1, 2으로 가로, 세로, 대각선 판단
static void dfs(int r, int c, int status) {
//도착지점에 도달한 경우
if (r == N - 1 && c == N - 1) {
count++;
return;
}
//가로, 세로, 대각선
for (int i = 0; i < 3; i++) {
//현재 상태에서 이동 불가능한 방향은 스킵
if ((status == 0 && i == 1) || (status == 1 && i == 0)) {
continue;
}
int nextR = r + dr[i];
int nextC = c + dc[i];
//범위를 벗어나거나 벽에 막힌 경우
if (nextR >= N || nextC >= N || house[nextR][nextC] == 1) {
continue;
}
//대각선 이동 시 추가 조건 확인
if (i == 2 && (house[nextR - 1][nextC] == 1 || house[nextR][nextC - 1] == 1)) {
continue;
}
//다음 칸으로 이동
dfs(nextR, nextC, i);
}
}
}DP
DP도 DFS와 동일한 방식이다. 메모이제이션 배열은 각 지점에 가로, 세로 그리고 대각선의 상태를 저장한다. 파이프의 초기 상태는 (0, 1)에 가로이므로 다음과 같다.
int[] dp = new int[N][N][3];
dp[0][1][0] = 1; //파이프 초기 상태그리고 모든 좌표에 대해 반복하면서 각 상태에 맞게 dp배열을 갱신해나간다.
전체 코드
//백준
public class Main {
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] house = new int[N][N];
int[][][] dp = new int[N][N][3];
for (int i = 0; i < N; i++) {
house[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
//초기 상태
dp[0][1][0] = 1;
//dp 계산
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (house[r][c] == 1) { //벽은 스킵
continue;
}
//가로 상태 갱신
if (c > 0) {
dp[r][c][0] += dp[r][c - 1][0]; //이전 가로 상태
dp[r][c][0] += dp[r][c - 1][2]; //이전 대각선 상태
}
//세로 상태 갱신
if (r > 0) {
dp[r][c][1] += dp[r - 1][c][1]; //이전 세로 상태
dp[r][c][1] += dp[r - 1][c][2]; //이전 대각선 상태
}
//대각선 상태 갱신
if (r > 0 && c > 0 && house[r - 1][c] == 0 && house[r][c - 1] == 0) {
dp[r][c][2] += dp[r - 1][c - 1][0]; //이전 가로 상태
dp[r][c][2] += dp[r - 1][c - 1][1]; //이전 세로 상태
dp[r][c][2] += dp[r - 1][c - 1][2]; //이전 대각선 상태
}
}
}
int result = dp[N - 1][N - 1][0] + dp[N - 1][N - 1][1] + dp[N - 1][N - 1][2];
System.out.println(result);
}
}
백엔드