[Programmers] 거리두기 확인하기

문제링크 👉 https://programmers.co.kr/learn/courses/30/lessons/81302?language=swift

 

문제 이해 

면접에 온 사람들이 거리를 두고 앉았는 지 유무를 묻는 문제입니다. 거리를 잘 두었는 지 판단하는 기준은 아래와 같습니다. 

- 자리 사이에 파티션이 존재하거나 자리가 대각선일 경우 O 

- 거리가 2인데 자리 사이에 책상이 놓여져 있다면 X

거리두기가 잘 지켜진 면접장은 1로, 지켜지지 않다면 0으로 반환하는 문제입니다. 

문제 풀이

dfs 그래프 문제입니다. 

응시자가 앉아있는 자리 P 일경우 dfs를 돌면서 옆에 칸막이면 패쓰, 책상이면 한번 더 dfs 돌아서 체크해주면 됩니다. 한 번 더 돌 경우, 이전에 확인했던 자리는 확인하면 안되므로 평소에는 visited 배열을 두었지만, 이 문제에서는 최대 2번만 dfs탐색을 하므로 함수 파라미터로 넘겨주었습니다. 

 

 

유용한 정보 -> String을 Array로 바꾸기

- solution함수의 파라미터 places는 "POOXP" 형태로 오기 때문에 이를 ["P","O","O","X","P"] 로 바꿔주어야합니다. 

- 방법 1. Array(string) 

- 방법 2. let array = string.map { String($0) }

 

방법 2로 풀었습니다.

참고 링크

 

코드 

import Foundation

var direction: [(Int,Int)] = [(-1,0),(0,1),(1,0),(0,-1)] // 위, 오른쪽, 아래, 왼쪽

func dfs(_ places: [[String]], _ xy: (Int,Int), _ count: Int, _ from: (Int, Int)) -> Bool {
    if count == 2 {
        if places[xy.0][xy.1] == "P" {
            return false
        } else {
            return true
        }
    }
    for dir in direction {
        let nextDirection: (Int,Int) = (xy.0 + dir.0, xy.1 + dir.1)
        if nextDirection.0 == from.0 && nextDirection.1 == from.1 { continue } // 이전에 찾은 곳
        if nextDirection.0 < 0 || nextDirection.0 >= 5 { continue } // 범위 밖
        if nextDirection.1 < 0 || nextDirection.1 >= 5 { continue } // 범위 밖
        if places[nextDirection.0][nextDirection.1] == "X" { continue } // 가림막
        if places[nextDirection.0][nextDirection.1] == "P" { return false }
        if places[nextDirection.0][nextDirection.1] == "O" {
            if dfs(places, nextDirection, count+1, (xy.0, xy.1)) == false {
                return false
            } else {
                continue
            }
        }
    }
    return true
}

func solution(_ places:[[String]]) -> [Int] {
    var result = [Int]()
    places.forEach {
        var places: [[String]] = []
        for oneLine in $0 {
            let arr = oneLine.map { String($0) }
            places.append(arr)
        }
        
        print(places)
        var flag = 0
        
        for (xIndex, x) in places.enumerated() {
            for (yIndex, y) in x.enumerated() {
                if y == "P" {
                    print(xIndex,yIndex)
                    if dfs(places, (xIndex,yIndex), 0, (0,0)) == false {
                        flag = 1
                        break
                    }
                }
            }
            if flag == 1 {
                break
            }
        }

        if flag == 0 {
            result.append(1)
        } else {
            result.append(0)
        }
    }
    return result
}