백준 - 로봇 청소기(Swift)

백준 - 로봇 청소기(Swift)

 

 

 문제 설명

 

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

14503번: 로봇 청소기

 

 

 

 나의 풀이

 

처음에는 완전탐색으로 DFS로 풀려고 했으나 예제2를 보니 0의 수가 막혀있지않은데 전체가 아닌 것을 보고 정확하게 구현을 해야하는 문제인 것을 알았다. 간단히 생각해보면 길이없을때 쭉 가다가 막혔을때 뒤쪽이 1이라면 바로 break해야하는 상황이기 때문에 완전탐색이 아닌 것을 알 수 있다.

 

하지만 방향에 대한 처리를 어떻게 해야할지 잘 모르겠어서 다른 사람의 풀이를 참고했는데 방향에 대한 변수를 dx, dy에 넣음으로써 구현할 수 있었다. 이렇게 하면 전진할 때와 후진할 때 현재 방향을 인덱스로 둠으로써 쉽게 구현을 할 수 있게 된다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let N = input[0], M = input[1]
let input2 = readLine()!.components(separatedBy:" ").map{Int($0)!}
var curR = input2[0], curC = input2[1], curD = input2[2] // 현재 x, y좌표와 방향
var map = [[Int]]()
for _ in 0..<N {
    map.append(readLine()!.components(separatedBy:" ").map{Int($0)!})
}


// 북 동 남 서
let dx = [-1, 0, 1, 0]
let dy = [0, 1, 0, -1]
var cnt = 0 // 전환한 횟수
var result = 1
map[curR][curC] = 2
while true {
    // 방향 전환
    curD -= 1
    if curD == -1 { curD = 3 }
    
    // 방향 전환한 값
    let nx = curR + dx[curD]
    let ny = curC + dy[curD]
    // 벽이거나 방문한 값이 아닐 때
    if map[nx][ny] != 1 && map[nx][ny] != 2 {
        map[nx][ny] = 2
        result += 1
        curR = nx
        curC = ny
        cnt = 0
        continue
    } else {
        cnt += 1 // 벽이거나 방문했다면 cnt만 증가
    }
    if cnt == 4 {
        curR -= dx[curD]
        curC -= dy[curD]
        cnt = 0
        // 뒤로 간 값이 벽이라면 종료
        if map[curR][curC] == 1 {
            break
        } 
    }
}

print(result)