[Swift][프로그래머스][BFS] 거리두기 확인하기

요구능력

BFS

 

문제풀이

문제에서 대놓고 BFS를 쓰라고 하고있다.

행렬로 이루어져있고 응시자와 응시자의 맨하탄거리가 2이하로 이루어져있고 중간에 파티션이 없다면 거리두기를 지키지 않은것으로 간주된다.

 

1) 맨하탄거리 구하는 함수

func manhatan(_ r1: Int, _ c1: Int, _ r2: Int, _ c2: Int) -> Bool{
    if abs(r1 - r2) + abs(c1 - c2) <= 2{
        return false
    }else{
        return true
    }
}

 

2) BFS

일반적인 BFS를 진행해주었는데, 이 BFS의 핵심은 파티션에 접근하게 됬을 때 파티션을 큐에 추가하지 않는다는 것이다.

파티션을 큐에 추가하게되면 파티션의 다음부분까지 추가해버리기 때문이다.

하지만, 이렇게 처리해도 아래 그림과 같은경우에는 O를 타고 P를 방문하게되면 맨하탄거리에 걸리게된다.

그래서, 파티션을 만났을 경우에는 그 파티션 건너편까지 방문처리를 해서 다음번에 방문하는일이 없도록하였다.

 

func bfs(_ x: Int, _ y: Int, _ arr: [[Character]]) -> Bool{
    var queue = [(Int, Int)]()//좌표, 거리
    var visited = Array(repeating: Array(repeating: false, count: 5), count: 5)
    queue.append((x, y))
    visited[x][y] = true
    
    while !queue.isEmpty{
        let (curX, curY) = queue.removeFirst()
        for i in 0..<4{
            let nx = curX + dx[i]
            let ny = curY + dy[i]
            
            if nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || visited[nx][ny]{continue}
            if arr[nx][ny] == "X"{
                if nx + dx[i] >= 0 && nx + dx[i] < 5 && ny + dy[i] >= 0 && ny + dy[i] < 5{
                    visited[nx + dx[i]][ny + dy[i]] = true
                }
                continue}
            if arr[nx][ny] == "P"{
                if !manhatan(x, y, nx, ny) {//맨하탄거리2이하일때
                   return false
                }
            }
            queue.append((nx, ny))
            visited[nx][ny] = true
        }
        
    }
    return true
}

 

3) Solution

places를 행마다 2차원 character배열로 바꿔서 bfs탐색을 용이하게했다.

isCorrect를 이용해서 bfs가 false를 한번이라도 반환하면 그 대기실은 거리두기가 지켜지지 않은것이므로 break를 사용해서 for문을 두개 다 빠져나온다.

func solution(_ places:[[String]]) -> [Int] {
    var result = [Int]()
    for i in places{
        var arr = [[Character]]()
        for j in i{
            arr.append(Array(j))
        }
        var isCorrect = true
        for i in 0..<arr.count{
            for j in 0..<arr.count{
                if arr[i][j] == "P"{
                    isCorrect = bfs(i, j, arr)
                    if !isCorrect{
                        break
                    }
                }
            }
            if !isCorrect{
                break
            }
        }
        if isCorrect{
            result.append(1)
        }else{
            result.append(0)
        }
    }
    return result
}

 

 

후기

기본기가 있는지 확인하는 문제같다.

 

코드

import Foundation
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]

func manhatan(_ r1: Int, _ c1: Int, _ r2: Int, _ c2: Int) -> Bool{
    if abs(r1 - r2) + abs(c1 - c2) <= 2{
        return false
    }else{
        return true
    }
}

func bfs(_ x: Int, _ y: Int, _ arr: [[Character]]) -> Bool{
    var queue = [(Int, Int)]()//좌표, 거리
    var visited = Array(repeating: Array(repeating: false, count: 5), count: 5)
    queue.append((x, y))
    visited[x][y] = true
    
    while !queue.isEmpty{
        let (curX, curY) = queue.removeFirst()
        for i in 0..<4{
            let nx = curX + dx[i]
            let ny = curY + dy[i]
            
            if nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || visited[nx][ny]{continue}
            if arr[nx][ny] == "X"{
                if nx + dx[i] >= 0 && nx + dx[i] < 5 && ny + dy[i] >= 0 && ny + dy[i] < 5{
                    visited[nx + dx[i]][ny + dy[i]] = true
                }
                continue}
            if arr[nx][ny] == "P"{
                if !manhatan(x, y, nx, ny) {//맨하탄거리2이하일때
                   return false
                }
            }
            queue.append((nx, ny))
            visited[nx][ny] = true
        }
        
    }
    return true
}

func solution(_ places:[[String]]) -> [Int] {
    var result = [Int]()
    for i in places{
        var arr = [[Character]]()
        for j in i{
            arr.append(Array(j))
        }
        var isCorrect = true
        for i in 0..<arr.count{
            for j in 0..<arr.count{
                if arr[i][j] == "P"{
                    isCorrect = bfs(i, j, arr)
                    if !isCorrect{
                        break
                    }
                }
            }
            if !isCorrect{
                break
            }
        }
        if isCorrect{
            result.append(1)
        }else{
            result.append(0)
        }
    }
    return result
}