[백준/Swift] 2638 : 치즈. 거북이 같은 내 코드 개선시키기...

 

 

• BOJ_2638.swift

• 2638 : 치즈/ 문제 소개
• 풀이 과정
• 초기 코드 부터 개선된 코드까지! 코드 구현

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

2638번: 치즈

2638 : 치즈 / 문제 소개

 

N(세로)*M(가로)의 모눈 종이 위에 치즈가 있다!!

모눈종이 edge부분에는 치즈가 존재하지 않는다.

치즈가 녹는데 조건이 있다.

외부의 공기(흰색 칸들)로부터 치즈 특정 칸이 외부 공기(흰색 공간) 2칸 이상 닿으면 해당 치즈는 1시간 이내로 녹게된다.

 

그림1의 c부분은  1시간 후에 녹는다.

그림 2의 경우 치즈 안에 공기가 있는데 이는 외부공기가 아니다. 따라서 그림 2의 1시간 뒤는 그림 3처럼 변하는데

이때 치즈 안 공기들이 외부공기와 접촉되면 외부 공기로 바뀌어 그림3의 1시간 뒤 결과는 치즈가 전부 녹게 된다.

 

풀이 과정

 

우선 주어진 입력은 치즈 안 공기, 외부 공기 할 것 없이 0으로 주어진다.

따라서 초기에 맵(모눈종이)에서 외부 공기는 0으로 표현했다.

그후 whlie문을 통해 bfs탐색을 하며 치즈가 녹는지?의 경우를 찾아서 녹는 경우의 치즈만 -1 처리를 하고 외부의 공기와 접촉이 되었는지 판단하기 위해 bfs탐색을 반복하며 진행했다.

초기 코드부터 개선된 코드 까지! 코드 구현

 

초기에 코드구현은 아래와 같이 했다.

 

주요 로직은 while문을 통해 치즈가 녹는 시간을 증가시키면서

매 시간마다 완전 탐색으로 치즈의 위치를 찾아

치즈가 녹는 함수 MeltingCheese(_:_:_:)를 통해 치즈의 각 칸마다 치즈가 녹는지 isMelting(_:_:) 함수를 통해 녹을 치즈는 queue의 isMelt를 true체크를 한 후 추후 다 녹이고,

외부 공기와 밀접한 내부 공기가 있는지 파악후 외부 공기로 변환하는 로직을 구현했다..

import Foundation
//탐색할 좌표
typealias Coord         = (x : Int, y : Int)
//치즈 탐색 할 좌표와 그 좌표가 녹아야 하는지 여부
typealias Element       = (point : Coord, isMelt: Bool)
//탐색 방향
let direction : [Coord] = [(-1,0),(1,0),(0,1),(0,-1)]
//맵 정보
class mapInfo
{
    let width  : Int
    let height : Int
    var map    : [[Int]]
    init()
    {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        height    = input[0]
        width     = input[1]
        map       = Array(repeating:[Int](),count:height)
        for i in 0..<height
        {
            map[i] = readLine()!.split(separator:" ").map{Int(String($0))!}
        }
    }
}
//외부공기와 마주한 내부 공기가 있는가?
func airChange(_ coord : Coord,_ m : inout mapInfo, _ visited : inout [[Bool]])
{
    var queue = [(coord.x,coord.y)]
    var index = 0
    visited[coord.y][coord.x] = true
    if m.map[coord.y][coord.x] == 0
    {
        m.map[coord.y][coord.x] = -1
    }
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx<0||nx>m.width-1||ny<0||ny>m.height-1 { continue }
            //이 조건은 외부공기와 마주한 내부 공기이다.
            if !visited[ny][nx] && m.map[ny][nx] == 0
            {
                visited[ny][nx] = true
                m.map[ny][nx]   = -1
                queue.append((nx,ny))
            }
            else if !visited[ny][nx] && m.map[ny][nx] == -1
            {
                visited[ny][nx] = true
                queue.append((nx,ny))
            }
        }
    }
}

// 치즈가 녹을 가능성이 있는가?
func isMelting(_ coord : Coord, _ map : mapInfo) -> Bool
{
    var cnt = 0
    for (dx,dy) in direction
    {
        let (nx,ny) = (coord.x+dx,coord.y+dy)
        if map.map[ny][nx] == -1
        {
            cnt += 1
        }
        if cnt >= 2
        {
            return true
        }
    }
    return false
}
//치즈를 탐색하며 치즈가 녹는지의 여부를 체크해 치즈를 녹인다.
func MeltingCheese(_ coord : Coord, _ m : inout mapInfo, _ visited : inout [[Bool]])
{
    var queue = [Element]()
    var index = 0
    queue.append((coord,isMelting(coord, m)))
    while queue.count != index
    {
        let ((curX,curY), _ ) = queue[index]
        index += 1
        direction.forEach
        {
            let (nx,ny) = (curX+$0.x , curY+$0.y)
            if nx<0||nx>m.width-1||ny<0||ny>m.height-1 { return }
            if !visited[ny][nx] && m.map[ny][nx] == 1
            {
                visited[ny][nx] = true
                if isMelting((nx,ny), m)
                {
                    queue.append(((nx,ny), true))
                }
                else
                {
                    queue.append(((nx,ny),false))
                }
            }
        }
    }
    //녹을 치즈들을 녹인다.
    for ((x,y),isMelt) in queue
    {
        if isMelt
        {
            m.map[y][x] = -1
        }
    }
}

func BOJ_2638()
{
    var m         = mapInfo()
    var time      = 0
    var isRunning = true
    while isRunning
    {
        var visited  = Array(repeating: Array(repeating:false, count:m.width), count : m.height)
        airChange((0,0), &m, &visited)
        time += 1
        isRunning    = false
        //완전탐색을 통해 치즈를 찾는다.
        for y in 0..<m.height
        {
            for x in 0..<m.width
            {
                if m.map[y][x] == 1 && !visited[y][x]
                {
                    visited[y][x] = true
                    isRunning     = true
                    MeltingCheese((x,y), &m, &visited)
                }
            }
        }
    }
    print(time - 1)
}
BOJ_2638()

음 성공적으로 맞았다. 그 후 여러 다른분들의 코드를 봤다.

그 중 applebuddy님의 코드를 유심히 살펴봤다..

 

visit 함수를 그냥 나처럼 Bool 타입으로 하지 않고 Int타입으로 했다.

그 이유는 처음부터 포문을 돌려 치즈의 위치를 찾아 해당 치즈가 2개 이상의 상온 공기와 접촉됬는지를 파악한 나와 달리

곧바로 외부 공기에서 bfs 탐색을 해가며 접촉한 치즈가 두번이상 방문됬는지!!를 파악한 후에

해당 치즈만 0으로 바꾸는 작업을 했다.

방문된 치즈 칸이 중첩해서 반복 방문될  경우 해당 치즈 칸의 visited방문된 횟수를 늘림으로써 내가 구현한 코드 isMelting를 대체했다..... 대단하다. 치즈 안 공간은 상관하지 않아도 된다.. 겉애가 치즈로 둘러 싸여 있을 테니까...

 

한가지 고민은 그렇다면 치즈 안공기가 상온과 접촉되서 바로 0에서  -1로되면 어떻게 하지?...

대답은 그것 또한 방문하면서 체크해 주면 된다는 것이다. (크으...) 저분은 천재 인거 같다.

 

수정된 코드

import Foundation
//탐색할 좌표
typealias Coord         = (x : Int, y : Int)
//탐색 방향
let direction : [Coord] = [(-1,0),(1,0),(0,1),(0,-1)]
//맵 정보
class mapInfo
{
    let width  : Int
    let height : Int
    var map    : [[Int]]
    init()
    {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        height    = input[0]
        width     = input[1]
        map       = Array(repeating:[Int](),count:height)
        for i in 0..<height
        {
            map[i] = readLine()!.split(separator:" ").map{Int(String($0))!}
        }
    }
}
func airChange(_ coord : Coord,_ isRunning : inout Bool,_ m : inout mapInfo, _ visited : inout [[Int]])
{
    var queue = [(coord.x,coord.y)]
    var index = 0
    visited[coord.y][coord.x] = -1
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx<0||nx>m.width-1||ny<0||ny>m.height-1 { continue }
            if m.map[ny][nx] == 1
            {
                visited[ny][nx] += 1
                isRunning = true
            }
            else if visited[ny][nx] == 0
            {
                visited[ny][nx] = -1
                queue.append((nx,ny))
            }
        }
    }
}

func BOJ_2638()
{
    var m         = mapInfo()
    var time      = 0
    var isRunning = true
    while isRunning
    {
        time += 1
        isRunning    = false
        var visited = Array(repeating: Array(repeating: 0, count: m.width), count: m.height)
        airChange((0,0),&isRunning, &m, &visited)
        for y in 0..<m.height
        {
            for x in 0..<m.width
            {
                if visited[y][x] >= 2
                {
                    m.map[y][x] = 0
                }
            }
        }
    }
    print(time - 1)
}
BOJ_2638()

그런데 이렇게 할 경우에 시간이 100ms가 됬다.

왜 난 100ms지..

 

시간 증진을 위한 코드는

visited체크를 먼저 한 다음에

치즈가 중첩된 방문인지, 공기와 접촉된 치즈인지를 판별한느 조건문을 먼저 달아주면 된다.

func airChange(_ coord : Coord,_ isRunning : inout Bool,_ m : inout mapInfo, _ visited : inout [[Int]])
{
    var queue = [(coord.x,coord.y)]
    var index = 0
    visited[coord.y][coord.x] = -1
    while queue.count != index
    {
        let (curX,curY) = queue[index]
        index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX+dx,curY+dy)
            if nx<0||nx>m.width-1||ny<0||ny>m.height-1 { continue }
            if visited[ny][nx] == -1
            {
                continue
            }
            if m.map[ny][nx] == 1
            {
                visited[ny][nx] += 1
                isRunning = true
            }
            else
            {
                visited[ny][nx] = -1
                queue.append((nx,ny))
            }
        }
    }
}

 이렇게 또 배워가는것 같다.

 

 

 

visit my github