[Swift][구현] 백준 14503번 (로봇청소기)

요구능력

구현

 

문제풀이

1) 그냥 입력받는 부분이다.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
let rcd = readLine()!.split(separator: " ").map{Int(String($0))!}
let r = rcd[0]
let c = rcd[1]
let d = rcd[2]
var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

 

2) visited의 경우 청소를 한곳을 체크하기위해서 생성했고, dx와 dy는 문제에서 요구하는 회전하는대로 움직이기 위해서 생성했다.

d의 경우 0 북, 1 동, 2 남, 3서라고 했으니까 로봇청소기가 바라보는 방향에서 왼쪽방향은 d를 -1한것이된다.

다만, 북 -> 서의경우는 따로 처리를 해줘야한다.

ex) 현재 동쪽을 바라보고 있는 상태로 다음 칸으로 이동했다면 d = 1이다.

그렇다면 우리가 왼쪽을 바라봐야 하니까 d = 0이된다.

그럼 우리는 동쪽에서 왼쪽인 북쪽으로 이동을 해야된다는 것이다.

그 이동을 위해서 dx와 dy를 선언한것이다.

let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]
var visited = Array(repeating: Array(repeating: false, count: m), count: n)

 

3) 처음에 로봇청소기가 출발할때는 출발지점을 청소하고 시작한다.

따라서 result = 1로 선언하였고 현재지점을 청소했으니 visited도 true로 처리해준다.

curD, curR, curC는 현재 d와 r과 c를 의미한다.

cnt는 회전횟수를 세어줄 프로퍼티이다.

var result = 1
visited[r][c] = true
var curD = d
var curR = r
var curC = c
var cnt = 0

 

4) 문제의 조건대로 while문을 돌리면서 청소기의 위치를 변경해준다.

while true{
    //방향전환
    curD -= 1
    if curD == -1 {curD = 3}//북 -> 서
    
    var nx = curR + dx[curD]
    var ny = curC + dy[curD]
    if !visited[nx][ny] && arr[nx][ny] != 1{//청소안했고, 벽이아니라면
        visited[nx][ny] = true
        curR = nx
        curC = ny
        result += 1
        cnt = 0
        continue
    }else{//청소를했거나 벽이면 왼쪽회전만 할테니까 회전수를 늘림
        cnt += 1
    }
    if cnt == 4{//회전수가 4번 다다르면 뒤로 후진
        cnt = 0
        nx = curR - dx[curD]
        ny = curC - dy[curD]
        if arr[nx][ny] != 1{ //벽이아니면 이동
            curR = nx
            curC = ny
        }else{ //벽이면 그만.
            break
        }
    }
}

후기

처음에 DFS로 접근했다가 도저히 아닌거 같아서 빡구현..

참고) DFS로 안되는이유 : DFS의 경우 재귀이기 때문에 문제에서 요구하는것처럼 되지않고 지나온길을 되돌아가서 다시탐색을 시작해서 안된다. 나의경우 예제2에서 깨달았는데 57이아닌 59가 답으로 나오더라는것이다..

 

코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
let rcd = readLine()!.split(separator: " ").map{Int(String($0))!}
let r = rcd[0]
let c = rcd[1]
let d = rcd[2]
var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
var result = 1
visited[r][c] = true
var curD = d
var curR = r
var curC = c
var cnt = 0
while true{
    //방향전환
    curD -= 1
    if curD == -1 {curD = 3}//북 -> 서
    
    var nx = curR + dx[curD]
    var ny = curC + dy[curD]
    if !visited[nx][ny] && arr[nx][ny] != 1{//청소안했고, 벽이아니라면
        visited[nx][ny] = true
        curR = nx
        curC = ny
        result += 1
        cnt = 0
        continue
    }else{//청소를했거나 벽이면 왼쪽회전만 할테니까 회전수를 늘림
        cnt += 1
    }
    if cnt == 4{
        cnt = 0
        nx = curR - dx[curD]
        ny = curC - dy[curD]
        if arr[nx][ny] != 1{
            curR = nx
            curC = ny
        }else{
            break
        }
    }
}
print(result)