[17070] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

전형적인 그래프 이론과 dp가 섞인 문제입니다.

파이프의 머리를 기준으로 위치를 잡아주면 (1,2)에서부터 (n,n)까지 이동하면 되는데 이때 파이프의 자세를 고려해줘야 합니다.

파이프가 가로로 누워있다면 45도밖에 못 움직이기에 가로로 평행이동하거나 대각선 아래로 이동하면서 오른쪽 아래 대각선이 될 것입니다.

이와 마찬가지로 세로인 경우도 제한 사항이 생기며 대각선인 경우만 제외하고 인접 리스트를 작성할 때 신경 써줘야 함을 알 수 있습니다.

 

다만, 대각선의 경우 벽이 있을 때 벽을 긁으면 안 되므로 대각선으로 이동할 때는 원래 파이프가 이동할 수 있는 모든 3가지의 경로상에 벽이 있으면 안 됩니다. (파이프가 3칸을 차지하기 때문이죠. 문제 조건에도 나와 있습니다.)

for(int i=0;i<n;i++){
   for(int j=0;j<n;j++){
      for(int k=0;k<3;k++){ //포즈 가로=0 , 세로=2, 대각선 =1
         if(zip[i][j]==1) continue;
         else{
         	//만약 현재 상태가 가로라면 세로로는 이동 할 수 없겠죠. 아래도 마찬가지입니다.
            if(i+1<n&&!zip[i+1][j]&&k!=0) adj[i][j][k].push_back({{i+1,j},2});
            if(j+1<n&&!zip[i][j+1]&&k!=2) adj[i][j][k].push_back({{i,j+1},0});
            // 대각선으로 이동하는 경우입니다. 파이프가 차지하는 공간에 벽이 없는 경우에만 이동 할 수 있습니다 (by 문제조건)
            if(i+1<n && j+1<n&&!zip[i+1][j+1]&&!zip[i+1][j]&&!zip[i][j+1]) adj[i][j][k].push_back({{i+1,j+1},1});
		 }	
	  }
   }
}

 

이런 점들을 신경 쓰면서 인접 리스트들을 파이프의 모양을 고려하면서 작성해준 다음, memozation을 활용하여 dfs를 돌려주면 쉽게 해결할 수 있는 문제가 됩니다.

 

처음으로 풀이를 써보는 게 생각보다 (github.io보다) 편하네요. 소스코드는 첨부하지 않겠습니다.