<Algorithm> 162. Puyo Puyo(BJO)

1. 11559번 Puyo Puyo(BJO)

   사용 알고리즘 :  DFS

• 이 문제는 시뮬레이션이 첨가된 문제인 것 같다는 생각이 들었다. 

• 설명이 보기 어렵게(?)되어 있어 아쉬웠지만 꽤 괜찮은 문제인것 같다.

• 한번에 통과할 수 있게 예외사항, 조건들을 완벽히 파악하는 시간이 필요할 것 같다.

문제에 대한 접근&생각

1. 같은색깔 뿌요가 4개 이상이면 터진다 -> DFS!
2. 뿌요는 아래로 내려온다 -> 중력!
3. 한번에 터질 수 있는 경우가 여러개 일경우 한번에 처리 -> 탐색조건!

내 코드 

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class Main {     static char[][] map;     static int count;     static boolean[][] visited;     static int[] dx = {0,0,1,-1};     static int[] dy = {1,-1,0,0};     static int chain;     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         map = new char[12][6];         /******************************          * DFS를 이용하여 같은 색깔 뿌요의 갯수를          * 탐색한다. 이때 4개이상일 경우 뿌요를          * 터트린다.(모든경우) 그리고 떠있는          * 뿌요들은 아래로 끌어내린 뒤 위과정을 반복하여          * 연쇄 된 횟수를 출력한다.          *******************************/         for(int i = 0; i < 12; i++) {             map[i] = br.readLine().toCharArray();         }         chain = 0;         solve();         System.out.println(chain);     }          private static void solve() {      while (true) {                     boolean check = false;         for(int i = 0; i < 12; i++) {             for(int j = 0; j < 6; j++) {                 if(map[i][j] !='.') {                     count = 0;                     visited = new boolean[12][6];                     dfs(i, j, map[i][j]);                     if(count >=4) {                         clean();                         check = true;                     }                 }             }         }                  if(check) {             chain++;             pullDown();         }         else break;       }     }     private static void pullDown() {         for(int i = 0; i < 6; i++) {             for(int j = 11; j >= 1; j--) {                 for(int k = j-1; k>=0; k--) {                     if(map[j][i] != '.') break;                     if(map[k][i] != '.' ) {                         map[j][i] = map[k][i];                         map[k][i] = '.';                         break;                     }                 }             }         }     }     private static void clean() {         for(int i = 0; i < 12; i++) {             for(int j = 0; j < 6; j++) {                 if(visited[i][j]) {                     map[i][j] = '.';                   }             }         }     }     private static void dfs(int x, int y, char puyo) {                  visited[x][y] = true;         count++;                  for(int i = 0; i < 4; i++) {             int nx = x + dx[i];             int ny = y + dy[i];             if(isBoundary(nx, ny) &&!visited[nx][ny]&& map[nx][ny] == puyo) {                 dfs(nx, ny, puyo);             }         }     }     public static boolean isBoundary(int nx,int ny) {         if(nx < 0 || ny < 0 || nx >= 12 || ny >= 6)              return false;         return true;     } }   Colored by Color Scripter

cs

참고 & 출처