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

문제의 링크 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

문제

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

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

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

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

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

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

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

가로

세로

대각선

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

 

풀이

DFS를 활용하면 쉽게 풀 수 있는 문제였습니다. 저는 처음에, visited 배열을 사용하지 않는 BFS 방식으로 문제를 풀려고 했으나, 계속 0%에서 시간초과가 발생하였습니다. 다만, 이러한 로직은 java에서는 안 되지만 C++에서는 된다는 것을 확인하였습니다. (꽤 억울하네요 ㅠㅠ)

N도 최대 16으로 크지 않은데 왜 시간초과가 났는지, 검색을 해 본 결과 아래 링크에서 해답을 찾을 수 있었습니다.

https://www.acmicpc.net/board/view/34633

글 읽기 - 파이프 옮기기1 테스트 케이스 추가

 

즉, 대부분 BFS로 시간 초과가 나신 분들은 중복된 케이스를 배제한 브루트포스로 풀이하였기때문에 발생한 것입니다. 다만, 저도 어떻게 고쳐야될 지 감이 잘 안잡혀서 결국 재귀함수를 활용한 DFS로 노선을 변경하였습니다.

(startlink님의 댓글 "BFS는 같은 정점을 한 번 방문해야 하는데, 같은 정점을 여러 번 방문하는 BFS와 같은 소스가 많습니다.

이건 브루트 포스를 Queue를 이용해서 BFS처럼 구현한 것입니다." 을 참조바랍니다.)

로직 자체는 상당히 단순했습니다. 거의 구현 문제 급으로, 7가지 경우의 수에 맞춰서 visited 배열도 필요 없이 주어진 조건 하에, x = N, y = N에 도달할 때까지 탐색합니다.

로직은 다음과 같습니다.

1. 파이프의 끝점을 기준으로 한다.

2. 파이프가 가로 방향일 경우, 동쪽으로 한 칸 또는 대각선으로 한 칸 이동한다.

3. 파이프가 세로 방향일 경우, 남쪽으로 한 칸 또는 대각선으로 한 칸 이동한다.

4. 파이프가 대각선 방향일 경우, 동쪽으로 한 칸 또는 남쪽으로 한 칸 또는 대각선으로 한 칸 이동한다.

 

파이프가 이동할 때, 벽이 없어야 하고 범위를 초과하면 안 된다는 점을 유의하면서 코드를 짜시면 되겠습니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int[][] map;
    static int ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
            }
        }
 
        ans = 0;
        DFS(1, 2, 0);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // x는 세로, y는 가로
    // direction이 0일 때는 파이프가 가로 방향, 1일 때는 세로 방향, 2일 때는 대각선 방향.
    public static void DFS(int x, int y, int direction) {
        if (x == N && y == N) { // 종료 조건
            ans++;
            return;
        }
 
        switch (direction) {
        case 0: // 파이프가 가로 방향일 경우, 갈 수 있는 경우는 동쪽과 대각선임.
            if (y + 1 <= N && map[x][y + 1] == 0) { // 동쪽
                DFS(x, y + 1, 0);
            }
            break;
        case 1: // 파이프가 세로 방향일 경우, 갈 수 있는 경우는 남쪽과 대각선임.
            if (x + 1 <= N && map[x + 1][y] == 0) { // 남쪽
                DFS(x + 1, y, 1);
            }
            break;
        case 2: // 파이프가 대각선일 경우, 갈 수 있는 경우는 동쪽과 남쪽, 대각선임.
            if (y + 1 <= N && map[x][y + 1] == 0) { // 동쪽
                DFS(x, y + 1, 0);
            }
 
            if (x + 1 <= N && map[x + 1][y] == 0) { // 남쪽
                DFS(x + 1, y, 1);
            }
            break;
        }
 
        // 파이프가 어떤 방향이든지, 대각선은 검사해서 가장 아래로 뺐음.
        if (y + 1 <= N && x + 1 <= N && map[x][y + 1] == 0 && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0) {
            DFS(x + 1, y + 1, 2);
        }
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.