[백준] 17070 파이프 옮기기 1 - DP + DFS + BFS JAVA

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

17070번: 파이프 옮기기 1

코드설명

DP 혹은 DFS 혹은 BFS를 활용하여 해결할 수 있습니다.

 

 

처음에 DP를 활용해서 풀려고했는데, 벽에 대한 이해가 부족하여 실패했습니다.

문제를 보면, 파이프는 벽이 존재할경우 파이프를 놓는것이 불가하다고 나와있습니다.

대각선의 경우로써 ( r, c ) 를 고려한다고 가정합니다.

이때, ( r, c) 에 파이프가 도달할 수 있는 경우는 dp[r-1][c-1][0] + dp[r-1][c-1][1] + dp[r-1][c-1][2] 입니다.

순서대로, 가로파이프 + 대각선 파이프 + 세로 파이프입니다. 이떄 조건으로

map[i][j] == 0 && map[i-1][j] == 0 && map[i][j-1] == 0

 각 위치에 벽이 존재하는지 확인하고 있습니다. 

이 경우에 저같은경우, (r, c)의 위치에서 위에 벽이 있는경우와 왼쪽에 벽이있는경우를 고려하여 진행하려했지만, 파이프가 대각선에 위치할경우, 세방향(상, 좌, 대각) 모두에 벽이 존재하지 않아야만 합니다. ( 대각선의 경우 3가지 방향 모두 벽이 없어야한다는 것을 꺠닫지 못해서 DP로 해결하는데 어려움이 있었습니다. ) 이유는 문제의 그림을 보거나 생각해보면, 파이프가 대각선인 경우 상, 좌에 겹쳐져 있는 모습을 볼 수 있습니다.

 

BFS와 DFS로도 해결이 가능합니다.

 

코드

 

DP로 해결코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N;
	public static int[][] map;
	public static int[][][] dp;
	public static int[] dx = {0, 1, 1}; //가로, 대각선, 세로 
	public static int[] dy = {1, 1, 0};
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	
    	map = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	dp = new int[N][N][3];
    	// 0 : 가로파이프, 1 : 대각선 파이프, 2 : 세로파이프 
    	dp[0][1][0] = 1;
    	for(int i=0;i<N;i++) {
    		for(int j=2;j<N;j++) { 
    			if( j - 1 >= 0 && map[i][j] == 0) { //가로파이프로 들어오는 경우 확인
    				dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1];
    			}
    			if( i -1 >=0 && j - 1 >= 0 && map[i][j] == 0 && map[i-1][j] == 0 && map[i][j-1] == 0) { //대각선 파이프로 들어오는 경우 확인
    				dp[i][j][1] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
    			}
    			
    			
    			if( i -1 >= 0 && j - 1 >= 0 && map[i][j] == 0) {
    				dp[i][j][2] = dp[i-1][j][2] + dp[i-1][j][1];
    			}
    		}
    	}
    	
    	answer = dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2];
    	System.out.println(answer);

    }
    
}

 

 

처음에 풀었던 코드입니다. 각 지점에서 다른 지점으로 파이프를 연결시키는것이 아닌, 미리 다른 곳에서 이전의 파이프를 확인하는 형식으로 진행하였습니다.

이렇게할경우, 벽이 있는경우 파이프를 밀어서 이동시킬 수 없다는 점,

올바르게 파이프의 개수를 셀 수 없다는점

과 같은 오류가 있습니다. 

그리하여, 시작점에서 다른 파이프로 이동하는 로직으로 수정했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static int N;
	public static int[][] map;
	public static int[][][] dp;
	public static int[] dx = {0, 1, 1}; //가로, 대각선, 세로 
	public static int[] dy = {1, 1, 0};
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	
    	map = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	dp = new int[N][N][3];
    	// 0 : 가로파이프, 1 : 대각선 파이프, 2 : 세로파이프 
    	dp[0][1][0] = 1;
    	dp[0][1][1] = 1;
    	
    	for(int i=0;i<N;i++) {
    		for(int j=2;j<N;j++) { //어처피 방향떄문에 1열과 2열은 가지못합니다.
    			if(map[i][j] == 1) continue;
    			

    			int nr, nc;
    			//1. 가로파이프 존재 확인
    			nr = i - dx[0];
    			nc = j - dy[0];
    			if( nr >= 0 && nr < N && nc >= 0 && nc < N) {
    				dp[i][j][0] += dp[nr][nc][0]; //왼쪽 파이프 확인
    				dp[i][j][1] += dp[nr][nc][0]; //왼쪽 파이프 확인
    			}
    			
    			//2. 대각선 파이프 존재확인
    			nr = i - dx[1];
    			nc = j - dy[1];
    			if( nr >= 0 && nr < N && nc >= 0 && nc < N) {
    				dp[i][j][0] += dp[nr][nc][1];
    				dp[i][j][1] += dp[nr][nc][1];
    				dp[i][j][2] += dp[nr][nc][1];
    			}
    			
    			
    			//3. 세로파이프 존재확인
    			nr = i - dx[2];
    			nc = j - dy[2];
    			if( nr >= 0 && nr < N && nc >= 0 && nc < N) {
    				dp[i][j][1] += dp[nr][nc][2];
    				dp[i][j][2] += dp[nr][nc][2];	
    			}
    			
    		}
    	}

    }
    
}