Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 백준
- SQL
- IT 면접 준비
- oracle ansi
- oracle ansi sql
- 개발자 면접 준비
- 백트래킹
- BFS
- DBASE&
- Spring Boot
- Gradle
- DFS
- 이중우선순위큐 java
- 이중우선순위큐 자바
- CJ DBASE&
- 면접 필수 질문
- 프로그래머스
- Java
- ansi sql 단점
- DP
- 디베이스앤 인턴 후기
- 프로그래머스 이중우선순위큐 java
- 위상정렬
- JPA
- ansi sql 장점
- 디베이스앤
- 프로그래머스 이중우선순위큐 자바
- 이분탐색
- 프로그래머스 이중우선순위큐
- 그리디
Archives
- Today
- Total
쉬운 프로그래밍
[알고리즘] 백준 16918 봄버맨 - JAVA 본문
알고리즘보다는 구현 과정에서 애를 먹었던 문제였다.
풀이에 가장 기초가 되는 생각은 홀수 시간에는 폭탄을 세팅하고, 짝수 시간에는 폭탄을 터뜨려야 한다는 것이다.
폭탄이 세팅되었다면, 세팅된 시각에 맞게 터뜨려지거나 옆칸의 폭발에 휘말려서 없어지는 로직을 짜야하는데
나는 폭탄입력시간만 가지고 노는 2차원 배열을 만들어서 했다.
정답 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static int r;
static int c;
static int n;
static final int[] dx = {0, 0, -1, 1};
static final int[] dy = {1, -1, 0, 0};
static char[][] map;
static int[][] bombCount;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s, " ");
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
map = new char[r][c];
visited = new boolean[r][c];
bombCount = new int[r][c];
for (int i = 0; i < r; i++) {
s = br.readLine();
for (int j = 0; j < c; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'O') {
bombCount[i][j] = 0;
}
else {
bombCount[i][j] = -1;
}
}
}
boom(0);
}
static void boom(int startSecond) {
for (int i = 1; i <= n; i++) {
if (i == 1) continue;
if (i % 2 == 0) {
setBomb(i);
}
else {
bfs(i);
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
static void bfs(int time) {
Queue<Location> queue = new LinkedList<>();
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] == 'O') {
if (time - 3 == bombCount[i][j]) {
queue.add(new Location(i, j));
}
}
}
}
while (!queue.isEmpty()) {
Location current = queue.poll();
map[current.x][current.y] = '.';
bombCount[current.x][current.y] = -1;
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
map[nx][ny] = '.';
bombCount[nx][ny] = -1;
}
}
}
}
static void setBomb(int time) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
map[i][j] = 'O';
if (bombCount[i][j] == -1) {
bombCount[i][j] = time;
}
}
}
}
static class Location {
int x;
int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'알고리즘 > DFS, BFS' 카테고리의 다른 글
[알고리즘] 백준 16234 인구 이동 - JAVA (0) | 2021.03.27 |
---|---|
[알고리즘] 백준 14502 연구소 (2) | 2021.03.18 |
[알고리즘] 백준 1697 숨바꼭질 - JAVA (0) | 2021.03.04 |
[알고리즘] 백준 2146 다리만들기 (0) | 2021.03.03 |
[알고리즘] 프로그래머스 - 네트워크 (0) | 2021.01.25 |
Comments