티스토리 뷰
1. 문제
https://www.acmicpc.net/problem/16918
2. 오답
- strikeBomb() : 폭탄을 터뜨리는 메서드
- "다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다"
- 위 조건에 의해 폭탄이 설치된 곳이 아닌, 이미 폭탄이 설치되어 있었던 좌표에 설치된 폭탄과 인접한 폭탄을 터뜨리는 메서드이다.
- visited를 사용하여 이미 폭탄이 설치되어 있었던 좌표를 저장한다. -> visited[idx1][idx2] = true
따라서 배열 전체를 탐색하면서 visited[idx1][idx2] = true인 폭탄과 인접한 폭탄을 터뜨리고, 현재 좌표에 폭탄이 없음을 의미하는 bombs에 '.'를 저장하고 visited에 false를 저장한다.
그러나 이는 잘못된 로직이다. if문에 의해 인접한 좌표에 있는 폭탄도 터지면서, 반복문을 진행하다가 폭탄이 설치되어 있는 좌표임에도 폭탄이 설치되지 않은 것으로(else문) 간주되어 폭탄을 다시 설치하는 문제가 있다. 즉, 폭탄이 터지면서 인접한 폭탄도 같이 터졌는데, 이후에 배열을 탐색하는 과정에서 폭탄이 인접해서 터진 좌표에 다시 폭탄을 설치하게 되는 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int R, C, N;
static char[][] bombs;
static boolean[][] visited;
static int[] dx = {0, 0, 0, -1, 1};
static int[] dy = {0, -1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] inputs = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::valueOf)
.toArray();
R = inputs[0]; // 가로
C = inputs[1]; // 세로
N = inputs[2]; // 몇 초?
visited = new boolean[R][C];
bombs = new char[R][C];
for (int i = 0; i < R; i++) {
char[] c = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
bombs[i][j] = c[j];
if (c[j] == 'O') {
// 모든 폭탄이 설치되기 전에, 폭탄이 설치된 좌표
// 즉, 터뜨릴 폭탄 좌표
visited[i][j] = true;
}
}
}
execute();
StringBuilder result = new StringBuilder();
for (int y = 0; y < R; y++) {
for (char c : bombs[y]) {
result.append(c);
}
result.append("\n");
}
System.out.println(result);
}
static void execute() {
// 1초 : 폭탄이 설치되지 않은 모든 곳에 폭탄 설치
// 2초 : 폭탄 터뜨린다. -> (1)visited=true, (2)인접한 폭탄, (3)터지지 않은 폭탄의 좌표를 visited에 저장
// 1 ~ 2 반복
for (int count = 1; count < N; count++) {
if (count % 2 == 0) {
strikeBomb(); // 폭탄을 터뜨린다.
} else {
// 폭탄이 설치되지 않은 곳에 폭탄을 설치한다.
putBomb();
}
}
}
static void putBomb() {
for (int y = 0; y < R; y++) {
Arrays.fill(bombs[y], 'O');
}
}
static void strikeBomb() {
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
if (visited[y][x]) { // 폭탄이 설치되어 있다면
for (int d = 0; d < 5; d++) { // 자신을 포함한 인접한 좌표의 폭탄을 같이 터뜨린다.
int cx = x + dx[d];
int cy = y + dy[d];
if (isNotOutOfRange(cx, cy)) {
bombs[cy][cx] = '.'; // 평지가 된다.
visited[cy][cx] = false;
}
}
} else {
visited[y][x] = true; // 폭탄 설치
}
}
}
}
static boolean isNotOutOfRange(int x, int y) {
return x >= 0 && y >= 0 && x < C && y < R;
}
}
3. 정답
따라서 strikeBomb() 메서드를 호출한 후에, 배열 전체를 탐색하면서 폭탄이 설치되어 있는 좌표(visited=true)를 갱신해야 한다.
폭탄이 설치된 좌표를 갱신하는 storeBombPos() 메서드를 작성하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int R, C, N;
static char[][] bombs;
static boolean[][] visited;
static int[] dx = {0, 0, 0, -1, 1};
static int[] dy = {0, -1, 1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] inputs = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::valueOf)
.toArray();
R = inputs[0]; // 가로
C = inputs[1]; // 세로
N = inputs[2]; // 몇 초?
visited = new boolean[R][C];
bombs = new char[R][C];
for (int i = 0; i < R; i++) {
char[] c = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
bombs[i][j] = c[j];
if (c[j] == 'O') {
// 모든 폭탄이 설치되기 전에, 폭탄이 설치된 좌표
// 즉, 터뜨릴 폭탄 좌표
visited[i][j] = true;
}
}
}
execute();
StringBuilder result = new StringBuilder();
for (int y = 0; y < R; y++) {
for (char c : bombs[y]) {
result.append(c);
}
result.append("\n");
}
System.out.println(result);
}
static void execute() {
// 1초 : 폭탄이 설치되지 않은 모든 곳에 폭탄 설치
// 2초 : 폭탄 터뜨린다. -> (1)visited=true, (2)인접한 폭탄, (3)터지지 않은 폭탄의 좌표를 visited에 저장
// 1 ~ 2 반복
for (int count = 1; count < N; count++) {
if (count % 2 == 0) {
strikeBomb(); // 폭탄을 터뜨린다.
storeBombPos(); // 폭탄이 설치된 좌표를 저장한다.
} else {
// 폭탄이 설치되지 않은 곳에 폭탄을 설치한다.
putBomb();
}
}
}
static void putBomb() {
for (int y = 0; y < R; y++) {
Arrays.fill(bombs[y], 'O');
}
}
static void storeBombPos() {
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
if (bombs[y][x] == 'O') {
visited[y][x] = true;
}
}
}
}
static void strikeBomb() {
for (int y = 0; y < R; y++) {
for (int x = 0; x < C; x++) {
if (visited[y][x]) { // 폭탄이 설치되어 있다면
visited[y][x] = false;
for (int d = 0; d < 5; d++) { // 자신을 포함한 인접한 좌표의 폭탄을 같이 터뜨린다.
int cx = x + dx[d];
int cy = y + dy[d];
if (isNotOutOfRange(cx, cy)) {
bombs[cy][cx] = '.'; // 평지가 된다.
}
}
}
}
}
}
static boolean isNotOutOfRange(int x, int y) {
return x >= 0 && y >= 0 && x < C && y < R;
}
}