파이프 만들기 2

Huisu·2024년 9월 6일
1

Coding Test Practice

목록 보기
116/119
post-thumbnail

문제

문제 설명

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

https://upload.acmicpc.net/0f445b26-4e5b-4169-8a1a-89c9e115907e/-/preview/

가로

https://upload.acmicpc.net/045d071f-0ea2-4ab5-a8db-61c215e7e7b7/-/preview/

세로

https://upload.acmicpc.net/ace5e982-6a52-4982-b51d-6c33c6b742bf/-/preview/

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

제한 사항

첫째 줄에 집의 크기 N(3 ≤ N ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.

입출력 예

입력출력
3
0 0 0
0 0 0
0 0 01
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 03
5
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 00
6
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 013
22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 04345413252

아이디어

완전 탐색으로도 풀리는 똑같은 문제

파이프가 가로일 때 int[][]

파이프가 세로일 때 int[][]

파이프가 대각선일 때 int[][]

제출 코드

package com.example.javacodingtest.boj.gold;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
 @author ranuinclulus
 @since
 @link https://www.acmicpc.net/problem/17069
 @timecomplex
 @performance 14444kb, 108ms
 @category
 @note
 */
public class four17069 {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder builder = new StringBuilder();
    static StringTokenizer tokenizer;
    static int n;
    static int[][] map;
    static long[][][]dp;

    public void solution() throws IOException {
        n = Integer.parseInt(reader.readLine());
        map = new int[n + 1][n + 1];
        dp = new long[n + 1][n + 1][3]; // i, j 좌표에 d 방향으로 도달할 수 있는 경우의 수

        for (int i = 1; i <= n; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        long result = 0;
        if (map[n][n] != 1) {
            dp[1][2][0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 3; j <= n; j++) {
                    if (map[i][j] == 1) continue;
                    // 가로
                    dp[i][j][0] = (dp[i][j - 1][0] + dp[i][j - 1][2]);

                    if (i == 1) continue;

                    // 세로
                    dp[i][j][1] = (dp[i - 1][j][1] + dp[i - 1][j][2]);

                    if (map[i - 1][j] == 1 || map[i][j - 1] == 1) continue;

                    // 대각선
                    dp[i][j][2] = (dp[i - 1][j - 1][0] 
							                    + dp[i - 1][j - 1][1] 
							                    + dp[i - 1][j - 1][2]);

                }
            }
            result = (dp[n][n][0] + dp[n][n][1] + dp[n][n][2]);
        }
        builder.append(result);
        writer.write(builder.toString());
        writer.flush();
    }

    public static void main(String[] args) throws IOException {
        new four17069().solution();
    }
}


참고 코드

package com.example.javacodingtest.boj.gold;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 @author ranuinclulus
 @since 2024.09.05
 @link https://www.acmicpc.net/problem/17070
 @timecomplex
 @performance 280608kb, 512ms
 @category
 @note
 */
public class five17070 {
    static class Pipe {
        int x;
        int y;
        int direction; // 가로 0, 세로 1, 대각선 2

        public Pipe(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }
    }

    static int[][] board;
    static int n;
    static int count = 0;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder builder = new StringBuilder();
    static StringTokenizer tokenizer;

    public void solution() throws IOException {
        n = Integer.parseInt(reader.readLine());
        board = new int[n][n];
        for (int i = 0; i < n; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
        if (board[n - 1][n - 1] == 0) {

            Queue<Pipe> toVisit = new LinkedList<>();
            toVisit.add(new Pipe(0, 1, 0));
            while (!toVisit.isEmpty()) {
                Pipe pipe = toVisit.poll();
                int x = pipe.x;
                int y = pipe.y;
                if (x == n - 1 && y == n - 1) {
                    count++;
                    continue;
                }

                if (pipe.direction == 0) {
                    if (x < n && y + 1 < n && board[x][y + 1] == 0) {
                        toVisit.add(new Pipe(x, y + 1, 0));
                    }
                    if (x + 1 < n && y + 1 < n && canCross(x, y)) {
                        toVisit.add(new Pipe(x + 1, y + 1, 2));
                    }
                } else if (pipe.direction == 1) {
                    if (x + 1 < n && y < n && board[x + 1][y] == 0) {
                        toVisit.add(new Pipe(x + 1, y, 1));
                    }
                    if (x + 1 < n && y + 1 < n && canCross(x, y)) {
                        toVisit.add(new Pipe(x + 1, y + 1, 2));
                    }
                } else if (pipe.direction == 2) {
                    if (x < n && y + 1 < n && board[x][y + 1] == 0) {
                        toVisit.add(new Pipe(x, y + 1, 0));
                    }
                    if (x + 1 < n && y < n && board[x + 1][y] == 0) {
                        toVisit.add(new Pipe(x + 1, y, 1));
                    }
                    if (x + 1 < n && y + 1 < n && canCross(x, y)) {
                        toVisit.add(new Pipe(x + 1, y + 1, 2));
                    }
                }
            }
        }

        builder.append(count);
        writer.write(builder.toString());
        writer.flush();

    }

    private boolean canCross(int x, int y) {
        return board[x + 1][y] == 0 && board[x][y + 1] == 0 && board[x + 1][y + 1] == 0;
    }

    public static void main(String[] args) throws IOException {
        new five17070().solution();
    }
}

0개의 댓글