[백준] code.plus(브루트 포스 Part 2,JAVA)17069번, 파이프 옮기기 2

문제 링크

17069번: 파이프 옮기기 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 파이프는 │, ─, \의 3가지 종류가 존재합니다.

2. 파이프는 45도로 회전이 가능하며 회전하는 방법은 문제에서 그림으로 설명하고 있습니다.

3. 시작할 때 파이프는 (1, 1), (1, 2)의 가로 파이프가 주어집니다.

4. (N, N)까지 가는 파이프를 놓을 수 있는 경우의 수를 결과로 출력합니다.

5. 파이프는 빈 칸(0)으로만 이동이 가능, 벽(1)으로는 이동 불가능합니다.

 

17070번 파이프 옮기기 1

[백준] code.plus(브루트 포스 Part 2,JAVA)17070번, 파이프 옮기기 1

위 문제와 내용은 동일하지만 입력되는 값의 범위가 훨씬 커진 상태입니다.

 

위 문제를 해결하는 로직은 그래도 하였지만 동적 프로그래밍의 메모이제이션을 이용하였습니다.

 

메모이제이션을 이용함으로써 중복되는 연산들을 줄임으로 범위는 커졌지만 똑같은 로직에서 제한 시간안에 해결할 수 있도록 구현하였습니다.

 

알고리즘 관련 내용 및 예제 관련 내용은 위 링크에서 자세히 설명하고 있으니 확인해주시기 바랍니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 이용해서 각 위치에서 (N, N)에 도착하도록 파이프를 놓는 메모이제이션을 구합니다.  
• 첫 시작 파이프 DP[0][1][0]에 대한 값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀와 메모이제이션을 통해 파이프를 놓을 때 (N, N)에 도착하는 경우를 구합니다.
• widthCheck함수는 파이프(-)을 연결하는 조건에 만족하는지 확인합니다.
• heightCheck함수는 파이프(|)을 연결하는 조건에 만족하는지 확인합니다.
• diagonalCheck함수는 파이프(\)을 연결하는 조건에 만족하는지 확인합니다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] map;		//칸 관련 정보 배열
    static long[][][] DP;	//메모이제이션 배열([y][x][파이프 형태])
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        DP = new long[N][N][3];
        //입력값 값 저장
        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());
        }
        map[0][0] = map[0][1] = 1;		//초기 파이프 (1, 1), (1, 2) 설정
        search(0, 1, 0);		//파이프 놓는 모든 경우 탐색
        bw.write(DP[0][1][0] + "");		//(N, N)에 도착하는 경우 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //파이프 연결 모든 경우 탐색
    static void search(int y, int x, int index){
        if(y==N-1 && x == N-1){		//파이프 (N, N)도착시
            return 1;
        }
        
        if(DP[y][x][index]!=0)
        	return DP[y][x][index];
        //이전 파이프 0번(-)일 때 연결
        if(index==0){
            if(widthCheck(y, x)){		// -연결
                map[y][x+1] = 1;
                DP[y][x][index] += search(y, x+1, 0);
                map[y][x+1] = 0;
            }
            if(diagonalCheck(y, x)){	// \연결
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 1;
                DP[y][x][index] += search(y+1, x+1, 2);
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 0;
            }
        }else if (index==1) {		//이전 파이프 1번(|)일 때 연결
            if(heightCheck(y, x)){	// | 연결
                map[y+1][x] = 1;
                DP[y][x][index] += search(y+1, x, 1);
                map[y+1][x] = 0;
            }
            if(diagonalCheck(y, x)){	// \ 연결
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 1;
                DP[y][x][index] += search(y+1, x+1, 2);
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 0;
            }
        }else{		//이전 파이프 2번(\)일 때 연결
            if(widthCheck(y, x)){	// - 연결
                map[y][x+1] = 1;
                DP[y][x][index] += search(y, x+1, 0);
                map[y][x+1] = 0;
            }
            if(heightCheck(y, x)){	// | 연결
                map[y+1][x] = 1;
                DP[y][x][index] += search(y+1, x, 1);
                map[y+1][x] = 0;
            }
            if(diagonalCheck(y, x)){	// \ 연결
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 1;
                DP[y][x][index] += search(y+1, x+1, 2);
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 0;
            }
        }
        return DP[y][x][index];
    }
    //0번(-)파이프 연결 조건 확인
    static boolean widthCheck(int y, int x){
        return x+1<N && map[y][x+1]==0;
    }
    //1번(|)파이프 연결 조건 확인
    static boolean diagonalCheck(int y, int x){
        return x+1<N && y+1<N && map[y][x+1]==0 && map[y+1][x]==0 && map[y+1][x+1]==0;
    }
    //2번(\)파이프 연결 조건 확인
    static boolean heightCheck(int y, int x){
        return y+1<N && map[y+1][x]==0;
    }
}