https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는
www.acmicpc.net
1726 : 로봇 / 문제 소개
로봇은 바라보는 방향으로 움직인다. 바라보는 방향은 동 서 남 북 가운데 하나이다.
로봇의 이동에는 제약조건이 있다.
- 명령 1 : GO K : k 는 1,2,3일 수 있다. 현재 바라보는 방향(로봇의 시선)에서 k칸 움직임
- 명령 2 :Turn dir : 움직이는 방향은 왼쪽, 오른쪽으로 90도 회전한다.
- 명령 1 또는 명령 2를 할 때마다 이동 횟수가 1씩 증가한다.
로봇은 1(벽)을 뛰어 넘을 수 없다. 0으로만 이동할 수 있다.
호호 이 두가지 규칙만 지키면서 최소한의 움직임으로 로봇의 도착지에 도달하는 최소 명령을 출력하면 된다.
풀이 과정
이 문제를 풀기 전에 유의 깊게 살펴 보아야 할 것은 문제에서 주어진 그림입니다.
맨 왼쪽 맨 위가 1,1로 시작합니다.
근데 입력칸의 가로 세로 길이는 N, M입니다. 그래서
로봇의 시작칸과 끝 칸에 -1 씩 해주거나 NM에 둘레 -1같은 패딩을 씌워야 합니다... ( 저는 로봇 시작칸 끝칸에 -1씩 했어요)
그리고 또 하나!!
로봇은 벽을 이동할 수 없는데 k == 1,2,3작업을 할 때 k==3일때 벽을 뛰어넘고 땅을 인식할 수 있는데 이러면 잘못된 코드입니다. 조심 해야 합니다. 계속 답이 6이 나왔었는데,, 알고보니 벽을 뛰어넘고선 땅을 인식 했었습니다.
그리고 또 하나!!
입력시 주어진 방향은
그림 2와 같이 주어집니다. (방향 다룰 때 조심해야합니다)
근데 저는 로봇이 만약 동쪽을 바라봤을 때 -1 하면 북을 향하도록, +1을 하면 남을 향하도록 direction을 사용하기 쉽게 바꾸었습니다.
/*
동 남 서 북
추후 이렇게 할 경우 특정 방향에서 +1, -1을 하면 left, right 로봇의 회전 시야를 다룰 때 편합니다.
*/
let direction : [(x:Int,y:Int)] = [(1,0),(0,1),(-1,0),(0,-1)]그 대신 이렇게 할 경우 예제입력에서 주어지는 로봇의 방향은
그림2와 같으므로
ex) 4 2 3 일 경우에는
남쪽이 3인데 일단 -1을 해주어야 합니다.
direction은 0부터 3까지의 index(동 남 서 북)로 가리킬 수 있는데
input의 방향은 그림2와 같이 1,2,3,4로 주어지기 때문에 시작 index가 1 크므로 -1 씩 해주어야 합니다. ( tempFront = input[2]-1)
그렇게 된다면 0 == 동 1 == 서 2 == 남 3 ==북 이 됩니다.
이때 저는 1과 2의 위치를 바꿔서 direction을 작성했음으로
시작과 끝의 방향을 direction에 맞춰서 입력해 주었습니다.
let start : (Int,Int,Int) =
{
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
tempFront = input[2] - 1
//서쪽이면 남으로 남쪽이면 서쪽으로 바꿈. 이래야 +90, - 90 하기 편함
if input[2] - 1 == 2
{
tempFront = 1
}
else if input[2] - 1 == 1
{
tempFront = 2
}
return (input[1]-1,input[0]-1,tempFront)
}()
let end : (Int,Int,Int) =
{
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
tempFront = input[2] - 1
//서쪽이면 남으로 남쪽이면 서쪽으로 바꿈. 이래야 +90, - 90 하기 편함
if input[2] - 1 == 2
{
tempFront = 1
}
else if input[2] - 1 == 1
{
tempFront = 2
}
return (input[1]-1,input[0]-1,tempFront)
}()
한 좌표에 대해서 로봇의 상태는 4개 존재합니다. (동 서 남 북)
이를 저장하기 위해 visited[M][N]개의 체크 방향 4개를 추가해야합니다. 저는 1,2,3,4 편하게 사용하기 위해 3차원 배열의 형태로 선언했습니다.
var visit = Array(repeating: Array(repeating: Array(repeating: false, count: m.width) , count: m.height) , count: 5)특정 방향(1,2,3,4)일 때 visit[특정방향][y좌표][x좌표]를 통해 방문 체크를 하며 진행했습니다.
그리고 이제 가장 중요한 로봇의 움직임을 bfs탐색으로 파악해 나가야합니다.
우선
명령1의 조건을 수행하기 위해서는 로봇이 현재 바라보고 있는 방향과 좌표가 필요합니다.
해당 좌표를 기준으로 한번, 두번, 3번 갔을 때를 for _ in 0..<3으로 체크하는데 이때 ,
방문 대상이 벽 또는!!! 맵의 밖을 벗어나면 탐색하지 못하도록 continue or break처리를 해주어야합니다.
로봇의 명령 2번째로는 현재 바라보고있는 방향에서 좌 또는 우로 회전만 하는 경우입니다.
이 또한 처리를 해주면 됩니다!
코드 구현
import Foundation
/*
bfs 탐색할 때 요소
x : 탐색 할 x 좌표
y : 탐색 할 y 좌표
front : 탐색할 로봇의 x,y좌표에서 로봇이 바라보고 있는 방향
count : 누적 명령 횟수
*/
typealias Element = (x: Int, y : Int, front : Int, count : Int)
/*
원래 주어진 입력에서의 로봇 방향은
동 : 1, 서 : 2, 남 : 3, 북 : 4
인데 좀 편하게 다룰려고
동 : 1, 남 : 2, 서 : 3, 북 : 4로 바꾼 direction을 선언했습니다.
따라서 추후 입력시 받게될 시작칸, 끝칸의 방향을 원본(1~4)에서 전체 1씩 뺀(0~3) 후에,
서쪽와 남쪽 숫자를 바꿔줍니다.
*/
let direction : [(x:Int,y:Int)] = [(1,0),(0,1),(-1,0),(0,-1)]
//맵 정보입니다. 길이, 맵 정보 있습니다
class mapInfo
{
let width : Int
let height : Int
var map : [[Int]]
init()
{
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
width = input[1]
height = input[0]
map = Array(repeating: [Int](), count:height)
for y in 0..<height
{
map[y] = readLine()!.split(separator:" ").map{Int(String($0))!}
}
}
}
/**
주어진 문제의 명령 조건 1,2에 따라 맵 안에서 로봇을 시작 지점 부터 도착 지점 까지 탐색 시킵니다!
- parameter m: 맵의 정보.
- parameter start: 시작 좌표.
- parameter end: 끝 좌표.
- param queue: 큐! 타입은 Element로 탐색 좌표, 그때 바라보는 방향, 누적 명령 횟수.
- param index: 큐를 훑기 위한 index.
- param visit: 특정 좌표에서 로봇의 front에 대한 방문 체크.
# Notes: #
1. while문 안에서의 for in구문은 로봇의 앞 전진 k == 1~3일때를 파악하는데 만약 맵을 벗어나거나 벽일 경우 그냥 break시켰습니다.
2. 이제 queue의 특정 탐색 좌표와 로봇이 바라보는 방향에 대해서 좌 우 회전 상태를 queue에 저장시킵니다.
주어진 문제는 무조건 시작지점에서 도착지점으로 도착합니다!
*/
func BFS(_ m : mapInfo, _ start : (x:Int,y:Int,front:Int), _ end : (x:Int,y:Int,front:Int))
{
var queue = [Element]()
var index = 0
var visit = Array(repeating: Array(repeating: Array(repeating: false, count: m.width) , count: m.height) , count: 5)
queue.append((start.x,start.y,start.front,0))
visit[start.front][start.y][start.x] = true
while queue.count != index
{
let (curX,curY,curFront,curCnt) = queue[index]
if end.x == curX && end.y == curY && end.front == curFront
{
print(curCnt)
return
}
index += 1
var nx = curX ,ny = curY
for _ in 0..<3
{
nx += direction[curFront].x
ny += direction[curFront].y
if nx < 0 || nx > m.width - 1 || ny < 0 || ny > m.height - 1 || m.map[ny][nx] == 1
{
break
}
if m.map[ny][nx] == 0 && !visit[curFront][ny][nx]
{
queue.append((nx,ny,curFront,curCnt + 1))
visit[curFront][ny][nx] = true
}
}
if !visit[(curFront+1)%4][curY][curX]
{
queue.append((curX,curY,(curFront+1)%4,curCnt + 1))
visit[curFront][curY][curX] = true
}
var tempFront = (curFront - 1)%4 == -1 ? 3 : (curFront - 1)%4
if !visit[tempFront][curY][curX]
{
queue.append((curX,curY,tempFront,curCnt+1))
visit[tempFront][curY][curX] = true
}
}
}
/*
여기서 주의 할 점은 시작, 끝 좌표와 방향을 나에게 유리하게 바꿔주기!
*/
func BOJ_1726()
{
let m = mapInfo()
var tempFront = 0
let start : (Int,Int,Int) =
{
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
tempFront = input[2] - 1
//서쪽이면 남으로 남쪽이면 서쪽으로 바꿈. 이래야 +90, - 90 하기 편함
if input[2] - 1 == 2
{
tempFront = 1
}
else if input[2] - 1 == 1
{
tempFront = 2
}
return (input[1]-1,input[0]-1,tempFront)
}()
let end : (Int,Int,Int) =
{
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
tempFront = input[2] - 1
//서쪽이면 남으로 남쪽이면 서쪽으로 바꿈. 이래야 +90, - 90 하기 편함
if input[2] - 1 == 2
{
tempFront = 1
}
else if input[2] - 1 == 1
{
tempFront = 2
}
return (input[1]-1,input[0]-1,tempFront)
}()
BFS(m, start, end)
}
BOJ_1726()
visit my github
'백준 PS일지 > DFS&BFS' 카테고리의 다른 글
| [백준/Swift] 17141 : 연구소2 (0) | 2022.07.22 |
|---|---|
| [백준/Swift] 2638 : 치즈. 거북이 같은 내 코드 개선시키기... (0) | 2022.07.21 |
| [백준/Swift] 14503 : 로봇 청소기 문제 뿌수기!! (0) | 2022.07.18 |
| [백준/Swift] 2251 : 물통 (0) | 2022.07.16 |
