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

문제 : 

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

14503번: 로봇 청소기

 

1. 문제 이해하기

• 이 문제는 문제 풀이를 시작하기 전에 문제를 잘 읽고 이해하고 푸셔야 할 것 같습니다.
• 크기 3 <= N X M <= 50의 그래프가 주어지고 현재 로봇의 위치(r, c), 현재 로봇이 바라보고 있는 방향 d가 주어집니다.
• 방향은 북: 0 동: 1 남: 2 서: 3

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향의 왼쪽부터 차례대로 인접 칸을 탐색
   1. 현재 방향의 왼쪽 인접 칸이 청소가 되지 않은 칸이라면, 그 방향으로 회전한 다음 한 칸을 전진하고 1부터 진행
   2. 현재 방향의 왼쪽 인접 칸이 청소가 된 칸이라면, 그 방향으로 회전만 하고 2번으로 돌아간다.
   3. 왼쪽 인접 칸을 모두 탐색하다가 인접한 모든 칸(네 방향의 칸)이 모두 청소를 했거나 벽이라면, 현재 방향을 유지한 상태로 한 칸 뒤로 이동하고 2번으로 돌아간다.
   4. 인접한 모든 칸(네 방향의 칸)이 모두 청소를 했거나 벽이면서, 현재 방향 기준 한 칸 뒤로 이동할 때 벽이라면 청소한 모든 칸의 개수를 출력하고 종료

벽을 통과할 수 없고, 청소했던 곳을 다시 이동할 수는 있으나, 청소 횟수가 증가하지는 않는다.

 

2. 문제 풀이 생각하기

1. 처음에는 현재 칸을 기준으로 현재 방향 쪽으로 쭉 갔다가 방향을 바꾸는 줄 알았는데 그것이 아니었습니다.
2. 먼저 현재 위치를 기준으로 인접한 칸 중 0이 아닌 칸의 개수를 저장하는 cnt 생성
3. while문 무한 루프로 시작합니다.
4. 현재 칸이 청소를 안 한 칸이면 2로 표시, 청소 횟수 + 1
5. 방향을 먼저 왼쪽으로 바꾸기(방향을 일단 바꾸고 전진할 것인지, 방향만 바꿀 것인지 판단)
6. 바꾼 방향으로 전진했을 때, 청소를 안 한 칸이면 전진 후, continue
7. 벽이거나, 청소를 이미 한 칸인 경우, cnt += 1, 인접한 칸 중 0이 없는 경우, 뒤로 갔을 때 벽이면 청소한 칸 출력 후 종료
8. 벽이 아니라면 현재 방향을 유지한 채로 뒤로 이동

 

두 번째 예제 입력으로 예시를 들어보겠습니다.

먼저 현재 위치입니다.

 

일부가 채워진 상황입니다.

해당 위치에서 현재 방향을 이미 청소했다면 왼쪽으로 계속 돌다가 안 채워진 곳을 이동해서 채웁니다.

 

계속 진행하다가 사방이 모두 0이 아니라면, 현재 방향을 유지한 상태로 뒤로 갑니다.

 

3. 차근차근 구현하기

import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var robot = readLine()!.split(separator: " ").map{Int(String($0))!}
var (i, j, d) = (robot[0], robot[1], robot[2])
var g = Array(repeating: Array(repeating: 0, count: m), count: n)
let di = [[-1, 0], [0, 1], [1, 0], [0, -1]]
var ans = 0
for i in 0..<n {
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    for j in 0..<m {
        g[i][j] = line[j]
    }
}

var cnt = 0 // 현재 위치 기준 인접한 칸 중 0이 아닌 칸 개수
while true {
    // 1
    if g[i][j] == 0 {
        g[i][j] = 2
        ans += 1
    }
    d = (d + 3) % 4 // 현재 방향에서 왼쪽 방향으로 바꾸기
    let ni = i + di[d][0]
    let nj = j + di[d][1]
    // 2 - a
    if g[ni][nj] == 0 {
        i = ni
        j = nj
        cnt = 0 // 이미 이동했기 떄문에 0
        continue
    }
    if g[ni][nj] != 0 {
        cnt += 1
        if cnt == 4 {
            cnt = 0 // 뒤로 가거나 종료할 것이기 때문에 0
            // 2 - b
            let tmpD = (d + 2) % 4
            let ni = i + di[tmpD][0]
            let nj = j + di[tmpD][1]
            // 2 - d
            if g[ni][nj] == 1 {
                print(ans)
                exit(0)
            }
            // 2 - c
            if g[ni][nj] != 1 {
                i = ni
                j = nj
            }
        }
    }
}

 

4. 피드백

• dfs 숙련도를 더 올려야겠습니다.