[백준 3085] 사탕 게임 (Swift)

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

 

브루트포스

아래와 같은 N*N 행렬에 사탕들이 종류별로 채워져 있음 -> 여기서 인접한 두개의 서로 다른 사탕을 서로 바꿨을 때,

행 또는 열에(가로 혹은 세로로) 가능한 긴 연속된 사탕의 개수가 뭔지 출력하는 문제이다.

CCP
CCP
PPC

 

접근방법

1. 초기 상태에서 가장 긴 연속 사탕 수 구하기 (BFS로 할 수 있을 것 같긴 한데..그냥 칸마다 구했습니다! (당당))

2. 바꿀 수 있는 두 캔디 찾기 (인접하면서 서로 다른 캔디 쌍)

3. 두 캔디 위치를 바꿨을 때 (swap) 두 캔디를 포함하는 가장 긴 연속 캔디 수를 구하고 현재 최대 길이랑 비교해서 갱신

이때, A, B 캔디라고 하면, A캔디 기준으로 가로, 세로로 가장 긴 연속 캔디 수 확인

B 캔디 기준으로 가로, 세로로 가장 긴 연속 캔디 수 확인

4. 그리고 매번 다시 위치 원래대로 되돌려주기

 

오답노트

같은 구조에 변수만 다른 코드를 여러번 쓰다보니까 변수들을 잘 관리하는 게 중요했다. (함수로 추상화 시켰으면 물론 좋았겠지만..^^)

c라고 써야되는걸 r이라고 썼어서 한번 대각선으로 캔디가 뒤바뀌는 경우가 생겼었고..;

원래 같은 행이나 같은 열에 있는 두 캔디의 위치를 바꾸는 거였으면, 두 캔디가 공유하는 행이나 열은 다시 계산하지 않았는데, 

ABAA같은 경우 AB를 서로 바꿨을 때 BAAA가 되면서 최대 길이가 또 갱신되기 때문에, 두 캔디를 기준으로 가로(행), 세로(열) 모두 계산을 다시해줘야 한다.

 

소스코드

import Foundation

func solution() -> Int {
    var result:Int = 0
    var map:[[Character]] = []
    let N:Int = Int(readLine()!) ?? 1
    
    for _ in 0..<N {
        let line:[Character] = Array(String(readLine()!))
        map.append(line)
    }
    
    // 초기 상태에 가장 긴 연속 사탕 수 구하기
    for r in 0..<N {
        for c in 0..<N {
            // r,c start (같은 행)
            var target = map[r][c]
            var cnt = 1
            var cc = c-1 // 옮겨가면서 최대 길이 체크
            while cc >= 0 {
                if map[r][cc] == target {
                    cnt += 1
                    cc -= 1
                } else {
                    break
                }
            }
            cc = c+1
            while cc < N {
                if map[r][cc] == target {
                    cnt += 1
                    cc += 1
                } else {
                    break
                }
            }
            if cnt > result {
                result = cnt
            }
            
            // r,c start (같은 열)
            cnt = 1
            var cr = r-1 // 옮겨가면서 최대 길이 체크
            while cr >= 0 {
                if map[cr][c] == target {
                    cnt += 1
                    cr -= 1
                } else {
                    break
                }
            }
            cr = r+1
            while cr < N {
                if map[cr][c] == target {
                    cnt += 1
                    cr += 1
                } else {
                    break
                }
            }
            if cnt > result {
                result = cnt
            }
        }
    }
    
    let dr = [-1,1,0,0]
    let dc = [0,0,-1,1]
    // process
    // 1. 바꿀 수 있는 두 캔디 찾기
    // 2. 바꿔서 최대 길이 달라지는지 확인
    for r in 0..<N {
        for c in 0..<N {
            // 상하좌우
            for i in 0..<4 {
                let nr = r + dr[i]
                let nc = c + dc[i]
                if nr >= 0 && nr < N && nc >= 0 && nc < N && map[r][c] != map[nr][nc] {
                    // 다른 캔디면 교환하고 최대 길이 갱신
                    // 교환
                    let temp = map[nr][nc]
                    map[nr][nc] = map[r][c]
                    map[r][c] = temp
                    // r,c start
                    // 같은 행
                    var target = map[r][c]
                    var cnt = 1
                    var cc = c-1 // 옮겨가면서 최대 길이 체크
                    while cc >= 0 {
                        if map[r][cc] == target {
                            cnt += 1
                            cc -= 1
                        } else {
                            break
                        }
                    }
                    cc = c+1
                    while cc < N {
                        if map[r][cc] == target {
                            cnt += 1
                            cc += 1
                        } else {
                            break
                        }
                    }
                    if cnt > result {
                        result = cnt
                    }
                    // 같은 열
                    cnt = 1
                    var cr = r-1 // 옮겨가면서 최대 길이 체크
                    while cr >= 0 {
                        if map[cr][c] == target {
                            cnt += 1
                            cr -= 1
                        } else {
                            break
                        }
                    }
                    cr = r+1
                    while cr < N {
                        if map[cr][c] == target {
                            cnt += 1
                            cr += 1
                        } else {
                            break
                        }
                    }
                    if cnt > result {
                        result = cnt
                    }
                    // r,c end
                    
                    // nr,nc start
                    // 같은 행
                    target = map[nr][nc]
                    cnt = 1
                    cc = nc-1 // 옮겨가면서 최대 길이 체크
                    while cc >= 0 {
                        if map[nr][cc] == target {
                            cnt += 1
                            cc -= 1
                        } else {
                            break
                        }
                    }
                    cc = nc+1
                    while cc < N {
                        if map[nr][cc] == target {
                            cnt += 1
                            cc += 1
                        } else {
                            break
                        }
                    }
                    if cnt > result {
                        result = cnt
                    }
                    // 같은 열
                    cnt = 1
                    cr = nr-1 // 옮겨가면서 최대 길이 체크
                    while cr >= 0 {
                        if map[cr][nc] == target {
                            cnt += 1
                            cr -= 1
                        } else {
                            break
                        }
                    }
                    cr = nr+1
                    while cr < N {
                        if map[cr][nc] == target {
                            cnt += 1
                            cr += 1
                        } else {
                            break
                        }
                    }
                    if cnt > result {
                        result = cnt
                    }
                    // nr,nc end
                    
                    // 다시 교환
                    map[r][c] = map[nr][nc]
                    map[nr][nc] = temp
                }
            }
        }
    }
    
    return result
}

print(solution())