봄버맨 - 백준(16918, 그래프 탐색)

🎯 봄버맨

봄버맨 - 16918, 그래프 탐색, 실버1

🧐 알고리즘[접근방법]

1. 장점의 개수로 2차원 배열 선언

2. N초 동안 해당 로직을 따르도록 구현

   1. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
   2. 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
   3. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
   4. 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
   • 3, 4번 반복

3. 폭탄 설치하는(3번) setBomb() 함수 구현

   • 폭탄이 설치되며, 설치되어 있는 폭탄들의 1초가 지난다.
   • 폭탄이 터지면 주변에 모든 것을 파괴, BFS()로 구현

4. 1초가 흐르는(4번) second() 함수 구현

👨‍💻 소스

import java.util.*;

public class Main {

  public static class Node {
    int x;
    int y;
    
    Node(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  
  public static int R;  // 열
  public static int C;  // 행
  public static int N;  // 시간 
  
  public static char[][] map;
  
  public static final int[] dx = {0, 0, -1, 1};
  public static final int[] dy = {-1, 1, 0, 0};
  
  public static void main(String[] args){

    Scanner sc = new Scanner(System.in);
    
    R = sc.nextInt();
    C = sc.nextInt();
    N = sc.nextInt();
    sc.nextLine();
    
    map = new char[R][C];
    
    for(int i = 0 ; i < R ; i++) {
      String s = sc.nextLine();
      for(int j = 0 ; j < C ; j++) {
        map[i][j] = s.charAt(j);
      }
    }

    int time = 0;
    while(time != N) {
      
      time++;

      if(time == 1) { // 처음 1초 동안 봄버맨은 아무것도 하지 않는다.
        second();
      } else {
        if(time % 2 == 0) { // 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
          setBomb();
        } else {  // 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
          second();
        }
      }

    }
    
    for(int i = 0 ; i < map.length ; i++) {
      for(int j = 0 ; j < map[i].length ; j++) {
        if(map[i][j] != '.') {
          map[i][j] = 'O';
        }
        System.out.print(map[i][j]);
      }
      System.out.println();
    }

  }
  
  public static void setBomb() {  // 폭탄 설치
    
    for(int i = 0 ; i < R ; i++) {
      for(int j = 0 ; j < C ; j++) {
        if(map[i][j] == 'O') {  // 폭탄일 때 시간 증가
          map[i][j] = '1';
        } else if(map[i][j] == '1') {
          map[i][j] = '2';
        } else if(map[i][j] == '2') { // 3초인 폭탄은 터진다.
          BFS(new Node(i, j));
        } else {
          map[i][j] = 'O';
        }
      }
    }
    
  }
  
  public static void second() {
    for(int i = 0 ; i < R ; i++) {
      for(int j = 0 ; j < C ; j++) {
        if(map[i][j] == 'O') {  // 폭탄일 때 시간 증가
          map[i][j] = '1';
        } else if(map[i][j] == '1') {
          map[i][j] = '2';
        } else if(map[i][j] == '2') {  // 3초인 폭탄은 터진다.
          BFS(new Node(i, j));
        }
      }
    }
  }
  
  public static void BFS(Node node) {	// 터지는 폭탄 주변 파괴![](https://imagedelivery.net/v7-TZByhOiJbNM9RaUdzSA/c8ee4c69-a0bc-444a-baaa-11f99b8fbf00/public)

    
    Queue<Node> q = new LinkedList<Node>();
    q.add(node);
    map[node.x][node.y] = '.';
    
    while(!q.isEmpty()) {
      Node n = q.poll();
      
      for(int i = 0 ; i < dx.length ; i++) {
        int x = n.x + dx[i];
        int y = n.y + dy[i];
        
        if(0 <= x && x < R && 0 <= y && y < C) {
          
          if(map[x][y] == '2') {
            q.add(new Node(x, y));
          }
          map[x][y] = '.';
        }
      }
      
    }
    
  }

}

🏅 결과

📖 관련 지식