[백준/Swift] 14503 : 로봇 청소기 문제 뿌수기!!

 

 

• BOJ_14503.swift

• 14503 : 로봇 청소기/ 문제 소개
• 풀이 과정
• 코드 구현

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

14503번: 로봇 청소기

14503 : 로봇 청소기 / 문제 소개

 

로봇은 NxM 크기의 직사각형 안에서 청소를 한다.

로봇 청소기는 청소기가 바라보는 방향이 있다. ( 북, 동, 남, 서 ) 중 1

청소를 할 때 규칙이 있다.

1. 현재 위치를 청소한다.

2.현재 위치에서 로봇이 바라보는 방향의 왼쪽 방향부터 차례대로 청소할 곳이 있는지 탐색한다.

  탐색 조건은

     2-1.  왼쪽 방향에 아직 청소하지 않은 공간 존재 -> 그 방향으로 회전 후 한칸 전진 후 1. 진행

     2-2. 왼쪽 방향 청소 없다면 왼쪽 회전 후 2번으로 돌아감.

     2-3. 네 방향 모두 청소 되어있거나 벽인 경우, 현재 위치에서 바라보는 방향의 반대 방향으로 한 칸 후진한다. 이때 바라보는 방향은 유지

     2-4. 네 방향 모두 청소 되어있거나, 벽 or 더 이상 후진 할 수 없는 경우 작동을 멈춘다.

---

input

첫째 줄 : 세로 가로 크기

둘째 줄 : 로봇 청소기 좌표, 바라보는 방향(0 : 북, 1  : 동, : 2 : 남, 3 : 서)

셋째 ~ N : 맵 정보

풀이 과정

 

이 문제를 보며 간과한 부분이 2개가 있었습니다.

1. 청소기가 바라보는 방향이 d == 0부터 북 서 남 동이 아니라 북 동 남 서

2. 후진 시 벽일 경우 뿐 아니라 더 이상 후진 할 수 없는 경우(맵을 벗어난 경우)

 

두가지 조건을 기억 하면서 문제를 풀어 나가야 합니다.

---

주어진 입력의 초기 로봇 청소기 방향에 따라서 정답이 달라집니다.

로봇 청소기의 방향에 따라 청소 할 수 있는 경로와 결과가 달라지기 때문입니다.

 

이 문제의 핵심은 방향 정하는 것 같습니다.

로봇이 앞을 바라보는 방향( == front로 부르겠습니다.)이

• 북쪽 일 때 90도 = 서
• 동쪽 일 때 90도 = 북
• 남쪽 일 때 90도 = 동
• 서쪽 일 때 90도 = 남

로봇이 바라보는 (front 시야)방향이 아래 그림1과 같을 때

그림1

탐색할 수 있는 경우는

case 1. 왼쪽에 청소할 공간이 있을때, (좌)

case 2. case1의 경우 왼쪽이 벽이거나 탐색했을 때 (아래)

case 3. case1 과 case2가 안되서 로봇이 아래쪽 시야를 바라볼 때 (우)

case 4. case1, case2 일때 탐색한 이후 후진해서 다시 돌아온 상태이거나, 벽인 경우 (위)

 

그래서 d == 0일때! d==0에 기준을 두어

특정 좌표에 대해서 앞으로 탐색해 나갈 좌표는 90도씩 회전한 방향의 좌표를 갖도록

//바라보는 방향에 따라 왼쪽으로 전진
let direction  = [(-1,0),(0,-1),(1,0),(0,1)]

이제 로봇의 방향이 d==0일때

d == 0이면 해당 좌표에 direction[0]을 .

case1이 안되서 case2로 전환한 경우 front(로봇 방향) == 좌 이면

해당 좌표에 + direction[1]

case2가 안되서 case3으로 전환한 경우 front == 아래

이면 해당 좌표에 + direction[2]

case 1도 x, case 2도 x case 3도 x case 4이면

해당 좌표에 direction[3]을 더해감으로 d == 0일 때 탐색 방향을 정할 수 있습니다.

---

d == 1( 로봇이 오른쪽을 바라봄)이라면?

direction[1] ,  이 방향이 막히면 direection[2] , 이 방향이 막히거나 청소한 경우면 direction[3], 청소하거나 막히면 direction[0]을  더해줌으로써 청소할 곳을 90도씩 회전하며 탐색해 나갈수 있습니다.

 

d==2 (아래) 면 현재 좌표에 direction[2] , 청소하거나 벽이거나 맵 밖인 경우, direction[3], 청소하거나 벽이거나 맵 밖인 경우 direction[0],  청소하거나 벽이거나 맵 밖인 경우direction[1]

 

d== 3도, d==4도 마찬가지입니다. 마찬가지입니다.

 

따라서 저는 dfs탐색 시 매개변수로 받은 좌표는 현재 방문했으면서 문제에서 주어진 2번 조건을 적용시켜야 함으로

특정 front일 때.

front == 1이면 direction[1] 부터 2, 3, 0

fornt == 2이면 direciton[2] 부터 3,4,0,1

...

func DFS(_ x : Int, _ y : Int, _ front : Int, _ clean : inout Int, _ m : mapInfo, _ visited : inout [[Bool]])
{
    var index = front
    for _ in 0..<4
    {
        let (dx,dy) = direction[index]
        index -= 1
        if index == -1
        {
            index = 3
        }
        let (nx,ny) = (x+dx,y+dy)
        .
        .
        .

이렇게 구해갔습니다.

 

---

또 중요한 게 있습니다.

로봇이 특정 방향으로부터 90도씩 회전하여 다시 특정 방향으로 갔다는 것은 더이상 청소를 할 곳이 없다는 뜻이므로 문제의 조건에 따라

후진을 해주어야 합니다.

후진 도 마찬가지로 d==0에 기준을 두어 설정했습니다.

let backDirect = [(0,1),(-1,0),(0,-1),(1,0)]

 

---

문제의 조건을 코드에 잘 적용 시켰다면

 

input

6 6
2 1 3
1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1

ans : 7 (5 아님)

 

input

12 9
0 0 0
0 0 0 1 1 0 0 0 1
0 0 1 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1
1 0 0 0 1 1 0 1 1
0 0 1 1 1 0 0 0 1
0 1 1 1 1 0 1 0 1
1 0 1 1 1 0 0 1 1
0 0 0 0 1 0 0 1 1
1 0 0 0 0 0 0 1 1
1 0 1 1 0 1 1 1 0
1 1 0 1 1 1 0 1 0
1 0 1 1 1 1 1 0 0

출처: https://joey09.tistory.com/122 [joie de vivre:티스토리]

ans : 5 

답이 나올 것입니다.

코드 구현

 

import Foundation
//바라보는 방향에 따라 왼쪽으로 전진
let direction  = [(-1,0),(0,-1),(1,0),(0,1)]
//바라보는 방향에 반대로 후진
let backDirect = [(0,1),(-1,0),(0,-1),(1,0)]

//맵 정보
class mapInfo
{
    let width  : Int
    let height : Int
    var map    : [[Int]]
    let start  : (x : Int, y : Int, direct : Int)
    init()
    {
        let input  = readLine()!.split(separator: " ").map{Int(String($0))!}
        height     = input[0]
        width      = input[1]
        let sPoint = readLine()!.split(separator:" ").map{Int(String($0))!}
        start      = (sPoint[1], sPoint[0], sPoint[2])
        map        = Array(repeating: [Int](),count: height)
        for y in 0..<height
        {
            map[y] = readLine()!.split(separator: " ").map{Int(String($0))!}
        }
    }
}

/**
 dfs탐색
 
 - parameter x: 현재 청소 할 x좌표.
 - parameter y: 현재 청소 할 y좌표.
 - parameter front: 로봇 청소기가 바라보는 방향.
 - parameter clean: 청소 누적 횟수.
 - parameter m: 맵 정보.
 
 # Notes: #
 1. 매개변수x,y 를 통해 현재 좌표에서 로봇이 바라보는 방향 front의 왼쪽 방향으로 회전 후 청소할 공간이 있을 때 전진하며 청소를 진행해간다.
 2. 바라보는 방향에서 90도 회전을 4번했는데 더이상 청소할 공간이 없다면
 3. 바라보는 방향 front에 대한 back 작업을 진행한다.
 4. 주의할 점이 맵의 벽이 1로 둘러진 경우만 생각할 게 아니라 맵의 0 0 좌표 일때도 로봇이 존재할 경우가 있다. 예외처리를 잘 해주어야 한다.
 */
func DFS(_ x : Int, _ y : Int, _ front : Int, _ clean : inout Int, _ m : mapInfo, _ visited : inout [[Bool]])
{
    var index = front
    for _ in 0..<4
    {
        let (dx,dy) = direction[index]
        index -= 1
        if index == -1
        {
            index = 3
        }
        let (nx,ny) = (x+dx,y+dy)
        if nx<0||nx>m.width-1||ny<0||ny>m.height-1
        {
            continue
        }
        if m.map[ny][nx] == 0 && !visited[ny][nx]
        {
            visited[ny][nx] = true
            clean += 1
            DFS(nx, ny, index, &clean, m, &visited)
        }
    }

    let (backxD,backyD) = backDirect[front]
    let (backX,backY)   = (x + backxD,y + backyD)
    if backX < 0 || backX > m.width-1 || backY < 0 || backY > m.height-1
    {
        print(clean)
        exit(0)
    }
    if m.map[backY][backX] == 1
    {
        print(clean)
        exit(0)
    }
    else
    {
        DFS(backX, backY, front, &clean, m, &visited)
    }
}
func BOJ_14503()
{
    let m     = mapInfo()
    var clean = 1
    var visited = Array(repeating: Array(repeating: false, count: m.width), count: m.height)
    visited[m.start.y][m.start.x] = true
    DFS(m.start.x, m.start.y, m.start.direct, &clean, m, &visited)
}
BOJ_14503()

 

visit my github