[BOJ] 17070 파이프 옮기기 1 - JAVA

1. 문제

17070번: 파이프 옮기기 1

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

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

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

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

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

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

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

가로

세로

대각선

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

---

2. 풀이

BFS(인듯 아닌 듯)

• 먼저 이 문제는 가능하긴 하지만 BFS를 권장하지 않는다고 말하고 싶다. BFS는 최단 경로를 찾을 때 유용한 알고리즘인데, 이 문제는 방문 여부와 상관없이 전부 여러 번 방문해야 하기 때문에 맞지 않다. queue를 사용한 브루트 포스 알고리즘이라고 보면 될 것 같다. 너비 우선적으로 완전탐색하기 때문이다.

클래스

• 방향, 위치를 저장하는 클래스다.

private static class Pipe {
   int r, c;
   int way;
 
   Pipe(int r, int c, int way) {
      this.r = r;
      this.c = c;
      this.way = way;
   }
}

입력

• 1인지 아닌지를 넣어서 벽일 때 true, 통로일 때 false를 house배열에 저장했다.
• 방향을 헷갈리지 않기 위해 변수에 인덱스 값을 넣었다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int H = 0, V = 1, D = 2;
 
int N = Integer.parseInt(in.readLine());
boolean[][] house = new boolean[N][N];
for (int i = 0; i < N; i++) {
   st = new StringTokenizer(in.readLine());
   for (int j = 0; j < N; j++) {
      house[i][j] = st.nextToken().charAt(0) == '1';//true:벽, false:지나갈 수 있음
   }
}

가지치기(아주 중요)

• 굳이 이 문제를 BFS(DFS도 마찬가지다)로 풀어야겠다면 가지치기가 필수다. 가지치기를 안 하면 무조건 시간 초과가 난다.
• 탐색을 하기 전에 찾아야 하는 위치가 벽인지 아닌지 체크한다. 벽이면 어차피 도달하지 못하는 곳이기 때문이다.

if (house[N - 1][N - 1]) {
   System.out.println(0);
   return;
}

탐색

• 첫 번째 파이프를 큐에 넣고 시작한다.
• 끝에 도달했다면(r이나 c가 N-1) result에 경우의 수+1을 하고 다음 노드 탐색으로 넘어간다.
• 이전 방향이 가로면 세로 방향을 탐색하지 않는다.
• 이전 방향이 세로면 가로 방향을 탐색하지 않는다.
• 세로, 가로, 대각선 방향을 탐색하는데 다음 좌표가 범위에 벗어나지 않고 벽도 아니라면 큐에 추가한다.
• 마지막으로 result값을 출력한다.

int result = 0;
 
Pipe pipe = new Pipe(0, 1, H);
Queue<Pipe> queue = new LinkedList<>();
queue.offer(pipe);
 
while (!queue.isEmpty()) {
   pipe = queue.poll();
   int way = pipe.way;
   if (pipe.r == N - 1 && pipe.c == N - 1) {
      result++;
      continue;
   }
 
   for (int i = 0; i < 3; i++) {
      if (way == H && i == V) continue;
      else if (way == V && i == H) continue;
      int nr, nc;
      if (i == H && (nc = pipe.c + 1) < N && house[pipe.r][nc]) {
         queue.offer(new Pipe(pipe.r, nc, H));
      }
      if (i == V && (nr = pipe.r + 1) < N && house[nr][pipe.c]) {
         queue.offer(new Pipe(nr, pipe.c, V));
      }
      if (i == D && (nr = pipe.r + 1) < N && (nc = pipe.c + 1) < N
            && house[nr][pipe.c] & house[pipe.r][nc] && house[nr][nc]) {
         queue.offer(new Pipe(nr, nc, D));
      }
   }
}
 
System.out.println(result);

 

 

DP

입력

• 6번째 줄에 보면 visited[][][] 배열이 있다. 3차원임에 주의하자!
• 가로, 세로, 대각선 값을 저장하기 위해 필요했다.
• H, V, D는 위에서 설명해서 넘어간다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int H = 0, V = 1, D = 2;
 
int N = Integer.parseInt(in.readLine());
int[][][] visited = new int[N][N][3];
int[][] house = new int[N][N];
for (int i = 0; i < N; i++) {
   st = new StringTokenizer(in.readLine());
   for (int j = 0; j < N; j++) {
      house[i][j] = Integer.parseInt(st.nextToken());
   }
}

탐색 원리

• 한 칸의 경우의 수를 직전 칸이 무엇인지 파악하기 위해 세 부분으로 분할한다. 대각선에서 온 경우의 수, 가로에서 온 경우의 수, 세로에서 온 경우의 수로 나눈다.
• 노란색 칸의 경우의 수를 찾으려면 파란색, 빨간색, 초록색 칸의 경우의 수를 각각 더해야 한다.
• 그런데 파란색 칸의 경우의 수 중 가로에서 온 경우는 노란 칸의 경우의 수가 될 수 없다. 가로방향은 세로 방향으로 움직일 수 없기 때문이다.
• 초록색 칸의 경우의 수 중 세로에서 온 경우도 노란색 칸의 경우의 수로 합할 수 없다. 세로 방향은 가로 방향으로 움직일 수 없기 때문이다.
• 빨간색 칸의 경우의 수는 노란색 칸의 대각선 위치이므로 어떤 방향에서 왔든 노란 칸의 경우의 수가 될 수 있다.

 

탐색 코드

• 맨 처음 파이프는 (0,1) 위치, 가로방향, 경우의 수가 하나이므로 visited[0][1][H]에 1을 저장한다. 문제에서는 (1,2)였는데 배열 크기 때문에 하나씩 뺐다.
• 파이프 초기 위치가 (0,0) (0,1)이므로 0번째 열은 언제나 0이다. 따라서 4번째 줄 j를 1부터 도는 것으로 정했다.
• 이제 위에서부터 아래로, 왼쪽에서부터 오른쪽으로 하나하나 탐색한다.
  • 첫 번째 줄의 2열까지는 초기 파이프이므로 건너뛴다.
  • 해당 위치가 벽이어도 건너뛴다.​
• 대각선: [i-1][j-1], [i][j-1], [i-1][j]가 벽이 아니고 범위에도 잘 맞을 때 직전 값의 모든 값을 더한다.
• 세로: [i-1][j]가 벽이 아니고 범위에도 잘 맞을 때 직전값의 세로, 대각선 값을 더한다.
• 가로: [i][j-1]가 벽이 아니고 범위에도 잘 맞을 때 직전값의 가로, 대각선 값을 더한다.

 

• 마지막으로 [N-1][N-1] 자리에 있는 모든 값을 더한 값을 출력한다.

visited[0][1][H] = 1;
 
for(int i=0;i<N;i++){
   for(int j=1;j<N;j++){  //어차피 맨 왼쪽은 못감
      if(i==0 && j<2) continue;
      if(house[i][j]==1) continue;
      if(i-1>=0 && house[i-1][j-1]!=1 && house[i-1][j]!=1 && house[i][j-1]!=1) {//대각선
         visited[i][j][D] = visited[i-1][j-1][H]+visited[i-1][j-1][V]+visited[i-1][j-1][D];
      }
      if(i-1>=0 && house[i-1][j]!=1) {//세로
         visited[i][j][V] = visited[i-1][j][V]+visited[i-1][j][D];
      }
      if(house[i][j-1]!=1) {//가로
         visited[i][j][H] = visited[i][j-1][H]+visited[i][j-1][D];
      }
   }
}
 
System.out.println(visited[N-1][N-1][H]+visited[N-1][N-1][V]+visited[N-1][N-1][D]);

---

3. 결과

• 결과에 캡쳐해놓은 걸 보면 알겠지만 시간 차이, 메모리 차이가 엄청나게 난다. 앞으로 완전 탐색 문제는 범위가 엄청 작지 않다면 무조건 DP라고 생각하고 풀어도 될 것 같다.
• 틀렸습니다=> 편의를 위해서 입력값 1(벽)을 -1로 바꿔놓았었는데 마지막에 그 값이 그대로 출력되면서(어떤 경우의 수도 도달하지 못했을 경우다) 틀렸다.
• 시간 초과 -> BFS... 가지치기를 안 해서 90%에서 시간 초과가 났다.
• 첫 번째 정답 코드 -> 위의 BFS코드다. 엄청 오래 걸리고 메모리도 많이 들었다.
• 두 번째, 세번째 정답코드 -> DP코드다. 둘 차이는 탐색할 때 j=1로 시작하느냐 마느냐 그 차이다. 두번째 코드가 j=0부터 시작해서 세 번째에는 시간이 더 적게 들 거라고 생각했지만 거기서 거기다. 메모리는 아주 조금 적게들긴 했다.