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

문제 링크

17070번: 파이프 옮기기 1

---

주의사항

• 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)으로는 이동 불가능합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 파이프를 놓는 모든 경우 진행합니다.

 

3. 모든 경우 탐색 후 (N, N)까지 갈 수 있었던 경우의 개수를 결과로 출력합니다.

 

파이프 연결

 

현재 연결되는 칸의 좌표를(y, x)로 생각하겠습니다.

 

─ 연결시 조건

[y][x+1] == 0(빈 칸) && x+1<N

 

│ 연결시 조건

[y+1][x]== 0(빈 칸) && y+1<N

 

\ 연결시

[y][x+1] == 0(빈 칸) && [y+1][x] == 0(빈 칸) && [y+1][x+1] == 0(빈 칸) &&

y+1 < N && x+1 < N

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 3

0	0	0
0	0	0
0	0	0

최초 파이프는 (1, 1), (1, 2)의 ─을 설치됩니다.

1	1	0
0	0	0
0	0	0

 

2. 파이프를 놓는 모든 경우 진행합니다.

 

─ 연결 → ─ 연결(X)

─ 연결 → \연결(X)

1	1	1
0	0	0
0	0	0

 

\연결 → ─ 연결(X)

\연결 → │ 연결(O)

\연결 → \ 연결(X)

1	1	1
0	1	1
0	0	0

1	1	1
0	1	1
0	0	1

 

3. 모든 경우 탐색 후 (N, N)까지 갈 수 있었던 경우의 개수를 결과로 출력합니다.

 

(N, N)까지 갈 수 있었던 경우 1개를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 이용해서 파이프를 놓는 모든 경우를 탐색합니다.
• 모든 경우를 탐색한 뒤 (N, N)에 도착하는 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해 파이프를 놓는 모든 경우를 탐색합니다.
• widthCheck함수는 파이프(-)을 연결하는 조건에 만족하는지 확인합니다.
• heightCheck함수는 파이프(|)을 연결하는 조건에 만족하는지 확인합니다.
• diagonalCheck함수는 파이프(\)을 연결하는 조건에 만족하는지 확인합니다.

 

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

public class Main {
    static int N, answer = 0;
    static int[][] map;		//칸 관련 정보 배열
    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];
        //입력값 값 저장
        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(answer + "");		//(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)도착시
            answer++;
            return;
        }
        //이전 파이프 0번(-)일 때 연결
        if(index==0){
            if(widthCheck(y, x)){		// -연결
                map[y][x+1] = 1;
                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;
                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;
                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;
                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;
                search(y, x+1, 0);
                map[y][x+1] = 0;
            }
            if(heightCheck(y, x)){	// | 연결
                map[y+1][x] = 1;
                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;
                search(y+1, x+1, 2);
                map[y][x+1]=map[y+1][x]=map[y+1][x+1] = 0;
            }
        }
    }
    //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;
    }
}