[백준 11559] puyo puyo (Swift)

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

남규 게임 그만해..

DFS & 시뮬레이션

뿌요뿌요 게임 = 테트리스 (근데 이제 같은 색깔 칸이 4칸이상 모이면 터지는)

터지면 빈 공간에 그 위에 있던 뿌요들이 내려와서 그 공간을 메운다.

다행히 위에서 계속 뿌요가 새로 추가되진 않음.

한판의 상황을 보고, 그때 터질 수 있는 모든 뿌요들이 터지는 데 이걸 1연쇄라고 한다.

연속적으로 몇번의 연쇄가 일어나는지 출력하는 문제

 

접근방법

1. 모든 칸을 보면서, 판에서 뿌요를 찾는다.

1-2. 그 뿌요와 인접한 같은 색 뿌요들을 찾아서 좌표를 모은다. (DFS)

1-3. 그 뿌요들이 4개 이상일 경우 터뜨린다 (그 자표들을 모두 "." 으로 바꿈)

2. 뿌요를 한번이라도 터뜨렸을 경우 연쇄 1번 추가로 카운팅, 한번도 못터뜨린 경우 종료

3. 이번 연쇄 때 터뜨린 뿌요로 인한 빈공간을 위에있는 뿌요들을 밀어서 채운다.

4. 뿌요를 터뜨리지 못할 때 까지 1~3번 반복

 

오답노트

3번 뿌요들을 밀어서 채우는 부분을 구현할 때 좀 어렵다고 생각했는데, 워낙 한정적인 크기여서 하나씩 보면서 swap 해줘도 되는 것 같았다.

 

소스코드

import Foundation

func solution() {
    
    var map:[[Character]] = []
    for _ in 0..<12 {
        map.append(Array(readLine()!))
    }
        
    let dr = [0,0,1,-1]
    let dc = [1,-1,0,0]
    
    func dfs(_ r:Int, _ c:Int, _ color:Character, _ list: inout [(Int,Int)], _ visit: inout [[Bool]]) {
        for i in 0..<4 {
            let (nr,nc):(Int,Int) = (r+dr[i], c+dc[i])
            if nr >= 0, nc >= 0, nr < 12, nc < 6, !visit[nr][nc], map[nr][nc] == color {
                visit[nr][nc] = true
                list.append((nr,nc))
                dfs(nr,nc,color,&list,&visit)
            }
        }
    }
    
    
    var cnt = 0
    while true {
        // 한 연쇄의 시작
        var isStarted = false
        for r in 0..<12 {
            for c in 0..<6 {
                if map[r][c] != "." {
                    // 같은 색 찾기 시작
                    var visit:[[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: 6), count: 12)
                    visit[r][c] = true
                    var list:[(Int,Int)] = [(r,c)]
                    dfs(r,c,map[r][c],&list,&visit)
                    
                    // 터짐
                    if list.count >= 4 {
                        isStarted = true
                        for (tr,tc) in list {
                            map[tr][tc] = "."
                        }
                    }
                }
            }
        }
        // 한 연쇄의 끝
        if isStarted {
            cnt += 1
        } else {
            break
        }
        
       // 맵 정리
        for c in 0..<6 {
            for cr in (0..<12).reversed() {
                if map[cr][c] != "." {
                    continue
                }
                // "." 지점 찾음
                // 뿌요 찾아야함
                var pr = cr-1
                while pr >= 0, map[pr][c] == "." {
                    pr -= 1
                }

                if pr < 0 {
                    break // 뿌요 없음
                }

                // 뿌요랑 . swap
                map[cr][c] = map[pr][c]
                map[pr][c] = "."
            }
        }
    }
    print(cnt)
}


solution()