[JS][백준]17070_파이프 옮기기 1

문제 번호

17070번: 파이프 옮기기 1

 

 

 

알고리즘 분류

DP, 그래프이론

 

문제 풀이

문제에서 파이프는 2칸을 차지한다고 하여서 처음에는 head 와 tail 로 나누어서 좌표를 기록하려 했다. 하지만 한쪽의 좌표만 기록해도 문제를 해결할 수 있다. 그래서 가장 처음상태의 (1,2) 에 있는 좌표만 사용하면서 문제를 해결한다. (1,1)에 있는 파이프는 신경쓰지 않아도 된다. 어차피 (1,1)은 고정이고 그 다음부터는 그래프 탐색과 다름없기 때문이다.

 

 그래프이론, DP, BF 풀이가 있다.

나는 문제에서 '방법의 수는 항상 1,000,000보다 작거나 같다.' 라고 했으므로 BF로 풀이하였다.

dxy라는 배열을 만들어서 0,1,2 인덱스에 가로, 세로, 대각선으로 이동시 좌표에 더해주어야 할 정수 값을 넣어준다.

let dxy = [ [0,1], [1,0], [1,1] ];

 

이제 브루트포스를 통해서 경로를 찾아주면된다. 

 단, 파이프를 가로에서 세로로, 세로에서 가로로 돌리는것은 불가능 하다고 문제에 나와있으니 주의해야한다. 

또한 파이프를 대각선으로 움직이는경우 파이프가 위치할 칸 외에도 (y-1,x) 와 (y,x-1) 도 검사해 주어야 한다.

function move(x,y,pipe){
  if(x === N && y === N)
    return answer++;
  else{
    for(let i=0; i<3; i++){
      let nextX = x + dxy[i][1];
      let nextY = y + dxy[i][0];
      // 방의 범위를 넘어갈때.
      if(nextX > N || nextY > N)
        continue;
      if(nextX > N || nextY > N)
        continue;

      // 가로->세로, 세로->가로 불가능.
      if(pipe === 0 && i === 1)
        continue;
      if(pipe === 1 && i === 0)
        continue;

      // 현재 대각선일때
      if(i===2){
        if(room[y][x+1] === 1 || room[y+1][x] === 1)
          continue;
      }

      if(room[nextY][nextX] === 0)
        move(nextX,nextY,i);
    }
  }
}

 

 문제에서 주어진 입력의 크기가 충분히 작았고 문제에서 '방법의 수는 항상 1,000,000보다 작거나 같다.' 라고 주어졌기  떄문에 BF로 풀이를 진행하였으나 주어진 메모리가 작거나 방법의 수가 많아지면 BF로는 문제풀이를 진행할 수 없을 것 같아서 DP를 사용하는 방법과 BFS를 사용하는 방법들을 찾아보았다.

 

DP

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

 알고리즘 문제를 풀면서 3차원 배열을 사용해본적이 거의 없어서 위의 방법이 더 참신했다. 
DP[y][x][놓아진상태] 를 사용해서 (y,x)에 '놓아진상태' 로 파이프를 옮기는 방법이다.

 

BFS

 

[ 백준 17070 ] 파이프 옮기기1 (C++)

 BFS로 탐색을 진행하는데 파이프의 현재상태에 따라서 push를 진행한다. 

 

 

특이사항

 문제를 잘 읽고 조건들을 잘 찾아내는게 중요했던 문제라고 생각된다.