[BOJ] 백준 11559. 뿌요뿌요

2024. 9. 18. 23:54· Java/BOJ

문제

https://www.acmicpc.net/problem/11559
 


풀이

bfs가 포함된 빡 구현 문제이다.
 
 제거할 뿌요를 bfs로 찾고, 삭제하고, 중력을 통해 재 정렬을 해야한다. 여러 그룹의 삭제될 뿌요가 한 텀에 있어도 연쇄는 한 번이라는 것을 잊으면 안된다.
 
 여기서 연속된 4개 이상이 연결된 뿌요를 찾아 제거해야하는데, 그냥 BFS를 사용해 탐색하면, ㅓ ㅏ ㅗ ㅜ 모양의 탐색은 visited에 걸려 탐색을 할 수가 없다. 이것은 단순하게 해결 가능한데, 최대 2번까지 방문을 허용하기만 하면 ㅓ ㅏ ㅗ ㅜ 탐색이 가능하게 된다.
 
중력에 의한 재정렬은 stack을 이용해 구현했다. 제거할 뿌요를 제외한 값을 stack에 push하고, 다시 map[][]의 아래부터 stack에서 pop을 하며 값을 채워넣었다.

코드를 보는 것이 더 이해가 쉬울 것 같다. 아래는 소스 코드이다.


소스 코드

import java.util.*;

public class B11559_뿌요뿌요 {
    static char[][] map;
    static int[][] visited;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static ArrayList<int[]> targets;
    static boolean stop = true;
    static int combo = 0;

    public static void main(String[] args) {
        input();
        while(true){
            findTargetAndBlast();
            dropPuyo();
            if(stop) break;
            combo++;
        }
        System.out.println(combo);
    }

    static void input(){
        Scanner sc = new Scanner(System.in);
        map = new char[12][6];
        for(int r=0;r<12;r++){
            String str = sc.next();
            for(int c=0;c<6;c++){
                map[r][c] = str.charAt(c);
            }
        }
    }
    
    static void findTargetAndBlast(){
        stop = true;
        for(int r=0;r<12;r++){
            for(int c=0;c<6;c++){
                if(map[r][c]!='.'){
                    visited = new int[12][6];
                    visited[r][c] = 1;
                    int cnt = bfs(r,c,map[r][c]);
                    if(cnt>=4){
                        stop = false;
                        blastPuyo();
                    }
                }
            }
        }
    }

    static void blastPuyo(){
        for(int[] target:targets){
            int r = target[0];
            int c = target[1];
            map[r][c] = 'T';
        }
    }

    static void dropPuyo(){
        for(int c=0;c<6;c++){
            Stack<Character> stack = new Stack<>();
            for(int r=0;r<12;r++){
                if(map[r][c]!='T'){
                    stack.push(map[r][c]);
                }
            }
            for(int r=11;r>=0;r--){
                if(!stack.isEmpty()) {
                    map[r][c] = stack.pop();
                }
                else map[r][c] = '.';
            }
        }
    }

    static int bfs(int R, int C, char value){
        Queue<int[]> queue = new ArrayDeque<>();
        targets = new ArrayList<>();

        queue.add(new int[]{R,C});
        targets.add(new int[]{R,C});
        int cnt = 1;
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int r = info[0];
            int c = info[1];

            for(int d=0;d<4;d++){
                int idr = r+dr[d];
                int idc = c+dc[d];
                if(idr<0||idc<0||idr>=12||idc>=6) continue;
                if(visited[idr][idc]>=2) continue;
                if(map[idr][idc]==value){
                    if(visited[idr][idc]==0) {
                        queue.add(new int[]{idr,idc});
                        cnt++;
                    }
                    else queue.add(new int[]{idr,idc});
                    visited[idr][idc]++;
                    targets.add(new int[]{idr,idc});
                }
            }
        }
        return cnt;
    }
}

'Java > BOJ' 카테고리의 다른 글

[BOJ] 백준 1707. 이분 그래프  (0) 2024.09.29
[BOJ] 백준 1461. 도서관  (1) 2024.09.14
[BOJ] 백준 25192. 인사성 밝은 곰곰이  (0) 2024.07.21
[BOJ] 백준 14658. 하늘에서 별똥별이 빗발친다  (0) 2024.06.30
[BOJ] 백준 1774. 우주신과의 교감  (1) 2024.06.24
'Java/BOJ' 카테고리의 다른 글
  • [BOJ] 백준 1707. 이분 그래프
  • [BOJ] 백준 1461. 도서관
  • [BOJ] 백준 25192. 인사성 밝은 곰곰이
  • [BOJ] 백준 14658. 하늘에서 별똥별이 빗발친다
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (177)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (32)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (5)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 김영한
  • 반효경
  • 프로그래머스
  • 인프런
  • 구현
  • 이석복
  • 큐
  • JCF
  • 한양대
  • OS
  • 레디스
  • 자바스크립트
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 백준
  • 스택
  • 자바
  • Java
  • 운영체제
  • BOJ
  • 네트워크

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 11559. 뿌요뿌요
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.