[백준, Java] 16919번, 봄버맨 2, 알고리즘 분류(구현)

문제 링크

16919번: 봄버맨 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 폭탄은 사방탐색(상, 하, 좌 ,우)로 터지며 연쇄 폭발은 일어나지 않는다.

2. 봄버맨의 행동은 문제에 설명과 동일하게 진행합니다.

3. 빈 칸은 '.', 폭탄은 'O'로 표현됩니다.

4. N초 후에 격자판에 상태를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 1초, 3초, 5초의 격자판의 상태를 구한 뒤 N값에 따라 격자판에 상태를 구합니다.

 

3. 격자판의 상태를 결과로 출력합니다.

 

규칙.

 

격자판에 상태를 시뮬레이션 돌리면 규칙을 발견할 수 있습니다.

 

 

예를 들어.

 

[초기, 1초]

.O

O.

 

[2초]

OO

OO

 

[3초]

..

..

 

[4초]

OO

OO

 

[5초]

..

..

 

[6초]

OO

OO

 

[7초]

..

..

 

다른 예시

 

[초기, 1초]

O.

..

 

[2초]

OO

OO

 

[3초]

..

.O

 

[4초]

OO

OO

 

[5초]

O.

..

 

[6초]

OO

OO

 

[7초]

..

.O

 

 

 

2초 → 4초 → 6초 : 동일

 

3초 → 7초 → 11초 : 동일

 

5초 → 9초 → 13초 : 동일

 

 

N이 1초일 때

 

초기 격자판 상태 출력!

 

N이 2의 배수일 때

 

모두  'O' 폭탄으로 채워진 격자판 상태

 

N mod 4 == 3일 때(N을 4로 나눈 나머지가 3일 때)

 

3초 뒤 격자판 상태

 

N > 1이고, N mod 1 == 1일 때(N이 1보다 크고, N을 4로 나눈 나머지가 1일 때)

 

5초 뒤 격자판 상태

 

이 규칙을 이용해서 N의 값에 따라 격자판 상태를 출력합니다.

 

 

예제입력 3.

1. 입력된 정보를 저장합니다.

6 7 5

.......
...O...
....O..
.......
OO.....
OO.....

 

2. 1초, 3초, 5초의 격자판의 상태를 구한 뒤 N값에 따라 격자판에 상태를 구합니다.

[초기상태, 1초]

 

.......
...O...
....O..
.......
OO.....
OO.....

 

[3초]

 

 

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

 

 

[5초]

 

 

...O...
....O..
.......
OO.....
OO.....

 

N = 5

 

▶ N > 1이고, N mod 1 == 1일 때(N이 1보다 크고, N을 4로 나눈 나머지가 1일 때)

 

 

= 5초 뒤 격자판 상태가 결과!!

 

3. 격자판의 상태를 결과로 출력합니다.

 

...O...
....O..
.......
OO.....
OO.....

 

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 R, C, N에 대한 값을 띄어쓰기 기준 나누었습니다.
• fill, setting 함수를 이용하여 1초, 3초, 5초의 격자판 상태를 구하였습니다.
• N의 값에 따라 격자판 상태를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• setting함수는 이전 상태에서 폭탄이 터졋을 때 상태를 구하는 함수입니다.
• fill함수는 폭탄이 터진 후 남은 공간을 'O'로 채우는 함수입니다.

 

결과코드

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

public class Main {
    static char[][][] versionMap;		//1초, 3초, 5초 격자판 상태 저장 배열
    static int[] dr = { -1, 1, 0, 0 };	//상하좌우 y변경값
    static int[] dc = { 0, 0, -1, 1 };	//상하좌우 x변경값
    static int R, C;

    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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        versionMap = new char[3][R][C];
        //1초뒤 격자판 상태 저장
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++)
                versionMap[0][i][j] = str.charAt(j);
        }
        //3초, 5초 뒤 격자판 상태 저장
        for(int i=0;i<2;i++){
            setting(i, i+1);
            fill(i+1);
        }
        
        //N이 2의 배수일 때 : 모든 격자판 'O'
        if (N % 2 == 0) {
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++)
                    sb.append('O');
                sb.append("\n");
            }
        }else {	
            //N이 1일 때 : 1초뒤 격자판 상태
            if (N == 1) {
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++)
                        sb.append(versionMap[0][i][j]);
                    sb.append("\n");

                }
            }else if (N % 4 == 3) {	//N mod 4 == 3일 때 : 3초 뒤 격자판 상태
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++)
                        sb.append(versionMap[1][i][j]);
                    sb.append("\n");
                }
            }else {	//N>1 And N mod 4 == 1일 때 : 5초 뒤 격자판 상태
                for (int i = 0; i < R; i++) {
                    for (int j = 0; j < C; j++)
                        sb.append(versionMap[2][i][j]);
                    sb.append("\n");
                }
            }
        }
        //격자판 상태 BufferedWriter 저장
        bw.write(sb.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //폭탄이 터졌을 때 사방탐색으로 '.'으로 변경하는 함수
    static void setting(int v1, int v2){
        //v1 : 이전 상태 버전, v2 : 현재가 될 상태 버전
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (versionMap[v1][i][j] == 'O') {
                    versionMap[v2][i][j] = '.';
                    for (int d = 0; d < 4; d++) {
                        int tempR = i + dr[d];
                        int tempC = j + dc[d];
                        if (inSpace(tempR, tempC))
                            versionMap[v2][tempR][tempC] = '.';
                    }
                }
            }
        }
    }
    //폭탄이 터진 후 남은 칸 'O'으로 채우는 함수
    static void fill(int version){
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (versionMap[version][i][j] == '.')
                    continue;
                versionMap[version][i][j] = 'O';
            }
        }
    }
    //격자판에 존재하는 좌표인지 확인하는 함수
    static boolean inSpace(int r, int c) {
        if (r >= 0 && c >= 0 && r < R && c < C)
            return true;
        return false;
    }
}