[BOJ] 백준 17070 파이프옮기기1 (JAVA)

문제 출처

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

17070번: 파이프 옮기기 1

 

 

---

풀이

2개의 연속된 칸을 차지하는 파이프를 3가지 방향으로 밀면서 회전시켜서 파이프의 한쪽 끝을 (N,N)으로 이동시키는 방법의 개수를 구하는 문제였습니다.

 

처음에는 dr, dc의 방향 배열과 위치와 가로, 세로, 대각선 중 어떤 상태인지를 가지는 클래스를 생성하여 bfs로 풀려고 했지만, 따져야 할 조건들이 많아 결국 dfs 재귀 형식으로 풀었습니다.

 

파이프는 두 칸을 차지하지만 왼쪽, 오른쪽, 아래방향으로만 진행하므로 파이프가 차지하는 왼쪽 칸은 신경 쓰지 않고, 오른쪽 칸만 이동하면서 (N, N)에 다다랐을 때 count변수를 증가시켜줬습니다.

 

문제에서 state변수가 가지는 의미는 아래와 같습니다.

• 1 : 파이프가 가로 상태
• 2 : 파이프가 세로 상태
• 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[][] map;
    static int count;

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

        N = Integer.parseInt(br.readLine());
        map = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(1, 2, 1);
        System.out.println(count);

    }


    private static void dfs(int r, int c, int state) {
        if (r == N && c == N) {
            count++;
            return;
        }

        if (state == 1) {
            //가로
            if (isIn(r, c + 1) && map[r][c + 1] == 0) {
                dfs(r, c + 1, 1);
            }

        } else if (state == 2) {
            //세로
            if (isIn(r + 1, c) && map[r + 1][c] == 0) {
                dfs(r + 1, c, 2);
            }

        } else if (state == 3) {
            //대각선
            if (isIn(r, c + 1) && map[r][c + 1] == 0) {
                dfs(r, c + 1, 1);
            }
            if (isIn(r + 1, c) && map[r + 1][c] == 0) {
                dfs(r + 1, c, 2);
            }
        }
        //대각선방향
        if (isIn(r + 1, c + 1) && map[r][c + 1] == 0 && map[r + 1][c] == 0 && map[r + 1][c + 1] == 0) {
            dfs(r + 1, c + 1, 3);
        }
    }


    private static boolean isIn(int r, int c) {
        return r > 0 && c > 0 && r <= N && c <= N;
    }

}