HackerRank - The Bomberman Game

문제출처 : HackerRank - The Bomberman Game

문제

요약
설치되면 3초후에 폭발하는 폭탄이 있습니다. 폭탄의 영향 범위는 폭탄의 상,하,좌,우의 셀로 Valid 에서 Clear 상태로 바뀝니다. 만약 폭발 범위 내에 다른 폭탄이 있다면 이 경우 함께 폭발하지 않고 폭탄이 제거됩니다.

매초 다음과 같은 일이 발생합니다.

1. 최초에 임의의 지점에 폭탄이 설치되어 있습니다.
2. 1초 동안 아무일도 발생하지 않습니다.
3. 다시 1초 후, 보드에 비어 있는 모든 지점에 폭탄이 설치됩니다.
4. 1초 후, 폭탄이 폭발합니다.
5. 3, 4의 과정이 반복됩니다.

n 초 후에 상태를 출력하세요.

입력형식

첫줄은 r, c, n 3개의 정수를 받습니다. r과 c는 각각 상태를 확인할 영역의 크기입니다. n 은 상태를 알고자 하는 시간(초) 입니다.

다음 줄부터 c 개의 문자가 r 회 입력됩니다. . 는 비어 있는 문자를, O 는 폭탄을 의미합니다.

제약사항

• 1 ≤ r, c ≤ 200
• 1 ≤ n ≤ 10^9

출력형식

n 초 후의 상태를 화면에 문자로 출력하세요.

풀이

초기 상태부터 n 초까지 실제로 각 초별로 변하는 상태를 계산하고, 최종시간이 될 경우 이를 화면에 출력해보도록 합니다. 문제를 이해하기 위해서 다음의 단계를 따라보았습니다.

1. 예시입력과 설명을 바탕으로 직접 손으로 상태를 그려봅니다. 이 때, 폭탄이 터지는 시간을 직접 표시하여 보드의 상태를 명확히(구별되도록) 표시할 수 있도록 수정하였습니다.

@0Sec      @1Sec		
0000000    0000000
0003000    0002000
0000300 -> 0000200
0000000    0000000
3300000    2200000
3300000    2200000


@2Sec	   @3Sec		
3333333    2220222
3331333    2200022
3333133 -> 2220002
3333333    0022022
2233333    0002222
2233333    0002222


@4Sec	   @5Sec		
1113111    0000000
1133311    0002000
1113331 -> 0000200
3311311    0000000
3331111    2200000
3331111    2200000

2. 문제에 기입된 내용을 바탕으로 각 초별로 무엇을 해줄 것인지 기입합니다.

// 0->1 ( 설치된 폭탄의 시간을 감소 )
// 1->2 ( 폭탄을 새로 설치 )
// 3->4 ( 설치된 폭탄의 시간을 감소 )
// 4->5 ( 폭탄을 새로 설치 )
// 5->6 ( 설치된 폭탄의 시간을 감소 ) 
// ...
@0Sec      @1Sec		
0000000    0000000
0003000    0002000
0000300 -> 0000200 ->
0000000    0000000
3300000    2200000
3300000    2200000


@2Sec	   @3Sec		
3333333    2220222
3331333    2200022
3333133 -> 2220002 ->
3333333    0022022
2233333    0002222
2233333    0002222


@4Sec	   @5Sec		
1113111    0000000
1133311    0002000
1113331 -> 0000200 ->
3311311    0000000
3331111    2200000
3331111    2200000

3. 이 작업을 통하여 2가지 작업을 해주어야 함을 확인하였습니다. 그리고 그것의 기준은 흐른 시간을 기준으로 나누어주면 되는 것을 확인 할 수 있었습니다. 이를 바탕으로 코드를 작성해보도록 합니다.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the bomberMan function below.
vector<string> bomberMan(int n, vector<string> grid) {

    // 좀 더 명확한 상태값으로 변경합니다.
    for (int i=0;i<grid.size();i++) {
        for (int j=0;j<grid[i].size();j++) {
            if (grid[i][j] == '.') {
                grid[i][j] = '0';
            } else if (grid[i][j] == 'O') {
                grid[i][j] = '3';
            }
        }
    }
    
    // 1초씩 증가시켜가면서 값을 변경해봅니다.
    for (int t=0;t<n;t++) {
        if (t%2==0) {
            // 설치된 폭탄의 시간을 감소
            for (int i=0;i<grid.size();i++) {
                for (int j=0;j<grid[i].size();j++) {
                    if (grid[i][j] == '1') {
                        if (i+1 < grid.size())
                            if (grid[i+1][j] != '1')
                                grid[i+1][j] = '0';
                        
                        if (i-1 >= 0)
                            if (grid[i-1][j] != '1')
                                grid[i-1][j] = '0';
                        
                        if (j+1 < grid[i].size())
                            if (grid[i][j+1] != '1')
                                grid[i][j+1] = '0';
                        
                        if (j-1 >= 0)
                            if (grid[i][j-1] != '1')
                                grid[i][j-1] = '0';
                        
                        grid[i][j] = '0';
                    } else if (grid[i][j] == '3') {
                        grid[i][j] = '2';
                    } else if (grid[i][j] == '2') {
                        grid[i][j] = '1';
                    }
                }
            }
        } else {
            // 폭탄을 새로 설치
            for (int i=0;i<grid.size();i++) {
                for (int j=0;j<grid[i].size();j++) {
                    if (grid[i][j] == '3') {
                        grid[i][j] = '2';
                    } else if (grid[i][j] == '2') {
                        grid[i][j] = '1';
                    } else if (grid[i][j] == '0') {
                        grid[i][j] = '3';
                    }
                }
            }
        }
    }

    for (int i=0;i<grid.size();i++) {
        for (int j=0;j<grid[i].size();j++) {
            if (grid[i][j] == '0') {
                grid[i][j] = '.';
            } else {
                grid[i][j] = 'O';
            }
        }
    }

    return grid;    

}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string rcn_temp;
    getline(cin, rcn_temp);

    vector<string> rcn = split_string(rcn_temp);

    int r = stoi(rcn[0]);

    int c = stoi(rcn[1]);

    int n = stoi(rcn[2]);

    vector<string> grid(r);

    for (int i = 0; i < r; i++) {
        string grid_item;
        getline(cin, grid_item);

        grid[i] = grid_item;
    }

    vector<string> result = bomberMan(n, grid);

    for (int i = 0; i < result.size(); i++) {
        fout << result[i];

        if (i != result.size() - 1) {
            fout << "\n";
        }
    }

    fout << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

4. 안타깝게도 13번 TestCase 부터 TimeOut 이 발생합니다. 모든 계산을 다 해보는 것을 원하지 않는 것 같습니다.

5. 다시 입력 예제로 돌아가서 좀 더 관찰을 해보도록 합니다.
   1초 후의 Pattern 과 5초 후의 Pattern 이 동일함을 관찰 할 수 있습니다.
   즉, 계산을 끝까지 할 필요가 없는 것으로 추측됩니다.

// 0->1 ( 설치된 폭탄의 시간을 감소 )
// 1->2 ( 폭탄을 새로 설치 )
// 3->4 ( 설치된 폭탄의 시간을 감소 )
// 4->5 ( 폭탄을 새로 설치 )
// 5->6 ( 설치된 폭탄의 시간을 감소 ) 
// ...
@0Sec      @1Sec		
0000000    0000000
0003000    0002000
0000300 -> 0000200 ->
0000000    0000000
3300000    2200000
3300000    2200000


@2Sec	   @3Sec		
3333333    2220222
3331333    2200022
3333133 -> 2220002 ->
3333333    0022022
1133333    0002222
1133333    0002222


@4Sec	   @5Sec		
1113111    0000000
1133311    0002000
1113331 -> 0000200 ->
3311311    0000000
3331111    2200000
3331111    2200000


@6Sec	   @7Sec		
3333333    2220222
3331333    2200022
3333133 -> 2220002 ->
3333333    0022022
1133333    0002222
1133333    0002222

6. 조금 더 시간을 진행해 보도록 하였습니다. 이러한 변화를 통해 얻은 결과는 아래와 같습니다. 그리고 이를 코드에 적용해주면 될 것으로 보입니다.

1초의 경우는 최초에 보드에 배치된 폭탄을 그대로 표시합니다.
2초의 경우는 폭탄을 가득채웁니다.
3초의 경우는 초기 배치됐던 폭탄이 터집니다. (2초에서 채운 폭탄중 초기 배치됐던 폭탄의 폭발 범위에 들지 않는 것은 남습니다.)
4초의 경우는 폭탄을 가득채웁니다.
5초의 경우는 2초에 배치했던 폭탄이 터집니다. (4초에 배치한 폭탄중 2초에 배치됐던 폭탄의 폭발 범위에 들지 않는 것은 남습니다.)
6초의 경우는 폭탄을 가득채웁니다.
7초의 경우는 3초에 배치했던 폭탄이 터집니다. (6초에 배치한 폭탄중 4초에 배치했던 폭탄의 폭발 범위에 들지 않는 것은 남습니다)

7. 짝수 시간이 흐른 경우, 보드의 모든 칸에는 폭탄이 가득합니다.
   최초로 폭탄이 가득찬 이후 부터 패턴이 반복되기 시작합니다. (배치됐던 폭탄의 폭발 범위 만큰 공백이 생기고 그외는 모두 폭탄이 배치됩니다. 서로 폭발하면서 제거할 수 없는 부분이 번갈아 가면서 남기 때문에 반복됩니다. 그 시점은 3초 이후 부터 입니다. 아래의 예를 살펴보면 확인 할 수 있습니다.)

@0Sec      @1Sec		
030        020
030     -> 020
003        002

@2Sec      @3Sec		
313        000
313     -> 000
331        200

@4Sec      @5Sec		
333        222
333     -> 022
133        002

@6Sec      @7Sec		
111        000
311     -> 000
331        200

8. 최종 코드는 다음과 같습니다.

※ bomberMan 함수만 작성하였습니다.

// Complete the bomberMan function below.
vector<string> bomberMan(int n, vector<string> grid) {

    // 좀 더 명확한 상태값으로 변경합니다.
    for (int i=0;i<grid.size();i++) {
        for (int j=0;j<grid[i].size();j++) {
            if (grid[i][j] == '.') {
                grid[i][j] = '0';
            } else if (grid[i][j] == 'O') {
                grid[i][j] = '3';
            }
        }
    }
    
    // 1초씩 증가시켜가면서 값을 변경해봅니다.
	// 0,1,2,3,4 초 후의 상태는 계산합니다.
	// 6초 이상인 경우는 4로 나눈 나머지 만큼으로 계산합니다.
	// 나머지가 1 인 경우(9초)는 5초 후의 값으로 계산합니다.
	if (n>5) {
		n = n%4;
		if (n==1) {
			n = 5;
		}
	}
    for (int t=0;t<n;t++) {
        if (t%2==0) {
            // 설치된 폭탄의 시간을 감소
            for (int i=0;i<grid.size();i++) {
                for (int j=0;j<grid[i].size();j++) {
                    if (grid[i][j] == '1') {
                        if (i+1 < grid.size())
                            if (grid[i+1][j] != '1')
                                grid[i+1][j] = '0';
                        
                        if (i-1 >= 0)
                            if (grid[i-1][j] != '1')
                                grid[i-1][j] = '0';
                        
                        if (j+1 < grid[i].size())
                            if (grid[i][j+1] != '1')
                                grid[i][j+1] = '0';
                        
                        if (j-1 >= 0)
                            if (grid[i][j-1] != '1')
                                grid[i][j-1] = '0';
                        
                        grid[i][j] = '0';
                    } else if (grid[i][j] == '3') {
                        grid[i][j] = '2';
                    } else if (grid[i][j] == '2') {
                        grid[i][j] = '1';
                    }
                }
            }
        } else {
            // 폭탄을 새로 설치
            for (int i=0;i<grid.size();i++) {
                for (int j=0;j<grid[i].size();j++) {
                    if (grid[i][j] == '3') {
                        grid[i][j] = '2';
                    } else if (grid[i][j] == '2') {
                        grid[i][j] = '1';
                    } else if (grid[i][j] == '0') {
                        grid[i][j] = '3';
                    }
                }
            }
        }
    }

    for (int i=0;i<grid.size();i++) {
        for (int j=0;j<grid[i].size();j++) {
            if (grid[i][j] == '0') {
                grid[i][j] = '.';
            } else {
                grid[i][j] = 'O';
            }
        }
    }
    return grid;    
}