[Swift] 2020 KAKAO BLIND RECRUITMENT 블록 이동하기

 

Problem

 

코딩테스트 연습 - 블록 이동하기

---

Solution

 

해당 문제는 BFS로 풀어야하는 문제입니다.

 

1. 현재 위치, 움직일 명령, 방향을 초기화해줍니다.

 

struct Current {
    var x:Int,y:Int,d:Direction,count:Int,past:Command
}

enum Command:CaseIterable {
    case up,down,left,right,rotateClockwise,rotateAntiClockwise,rotateClockwise2,rotateAntiClockwise2
}

enum Direction:CaseIterable {
    case right,down,left,up
}

 

현재 위치는 x,y,방향,시간,과거에 움직인 명령을 프로퍼티로 가집니다.

 

명령은 위,아래,왼쪽,오른쪽과 로봇의 첫번째를 기준으로 시계방향,반시계 방향,두번째를 기준으로 시계방향,반시계방향

 

총 8가지의 명령을 설정해줍니다.

 

(아래처럼 로봇의 1번째와 2번째라고 부르겠습니다.)

 

 

방향은 현재 로봇의 1번째 기준으로 두번째 로봇이 어느 방향에 있는지를 나타냅니다.

 

 

 

2. 명령에 따라 현재 위치를 움직여줍니다.

 

//명령에 따라 움직인 위치를 반환
func move(current:Current,command:Command) -> Current {
    var newCurrent = current
    let allDirection = Direction.allCases
    let index = allDirection.firstIndex(of: current.d) ?? -1
    
    switch command {
    case .up:
         newCurrent.y -= 1
     case .down:
         newCurrent.y += 1
     case .left:
         newCurrent.x -= 1
     case .right:
         newCurrent.x += 1
    case .rotateClockwise:
        newCurrent.d = index == 3 ? .right:allDirection[index+1]
    case .rotateAntiClockwise:
        newCurrent.d = index == 0 ? .up:allDirection[index-1]
    case .rotateClockwise2:
        newCurrent = current2(current: current)
        newCurrent.d = index == 0 ? .up :allDirection[index-1]
    case .rotateAntiClockwise2:
        newCurrent = current2(current: current)
        newCurrent.d = index == 3 ? .right :allDirection[index+1]
    }
    return newCurrent
}

 

3. 이동한 위치가 가능한 위치에 있는지 확인해줍니다.

 

우선 현재 위치가 지도 내에 있는지 확인하고

 

현재 위치가 1이 아닌지 확인하고 

 

현재 위치가 이미 방문한 위치가 아닌지 이렇게 총 3가지를 확인합니다.

 

여기서 만약 현재 위치의 과거가 회전해서 도착한 위치라면 

 

각 맨하튼 거리가 1이 아니였는지 확인해줍니다.

 

//이동한 위치가 가능한 위치인지 확인
func isEnabled(current:Current,b:[[Int]]) -> Bool {
    let second = current2(current: current)
    //현재 로봇이 지도 내에 있는지 확인
    if 0..<b.count ~= current.x && 0..<b.count ~= current.y && 0..<b.count ~= second.x && 0..<b.count ~= second.y {
        //현재 로봇이 있는 곳이 모두 0인지 확인
        if b[current.y][current.x] == 0 &&  b[second.y][second.x] == 0 {
            //현재 로봇이 있는 곳이 이미 지나간 곳이 아닌지 확인
            if !dontMove[current.d]![current.y][current.x] {
                //시계방향으로 회전했을 경우 각 현재 위치 맨하튼 거리가 0인지 확인
                if current.past == .rotateClockwise || current.past == .rotateClockwise2{
                    return b[current.y+clockManhattan[current.d]!.1][current.x+clockManhattan[current.d]!.0] == 0
                //반시계방향으로 회전했을 경우 각 현재 위치 맨하튼 거리가 0인지 확인
                }else if current.past == .rotateAntiClockwise || current.past == .rotateAntiClockwise2{
                    return b[current.y+antiClockManhattan[current.d]!.1][current.x+antiClockManhattan[current.d]!.0] == 0
                }else {
                    return true
                }
            }
        }
    }
    return false
}

 

4. BFS를 이용해서 지도의 맨 끝에 도착할 때까지 반복해줍니다.

 

큐를 이용해서 현재 위치를 담고 로봇이 가능한 위치에 있는지 확인하고

 

가능하다면 모든 명령에 따라 움직이게 하고 큐에 담아준 뒤 

 

지도의 맨 끝에 로봇이 도착했다면 해당 시간을 반환해줍니다.

 

func findMinCountByBFS(board:[[Int]]) -> Int {
    let allCommand = Command.allCases
    var queue:[Current] = [Current(x: 0, y: 0, d: .right, count: 0, past: .right)]
    
    while !queue.isEmpty {
        var first = queue.removeFirst()
        let second = current2(current: first)
        
        if isEnabled(current: first, b: board) {
            if (first.x == board.count-1 && first.y == board.count-1) || (second.x == board.count-1 && second.y == board.count-1){
                return first.count
            }
            
            //방문 표시
            dontMove[first.d]![first.y][first.x] = true
            //카운트 1증가
            first.count += 1
            
            //명령별로 움직여줌
            for command in allCommand {
                var newCurrent = move(current: first, command: command)
                newCurrent.past = command
                queue.append(newCurrent)
            }
        }
    }
    return 0
}

---

Source Code

 

	struct Current {
	var x:Int,y:Int,d:Direction,count:Int,past:Command
	}
	enum Command:CaseIterable {
	case up,down,left,right,rotateClockwise,rotateAntiClockwise,rotateClockwise2,rotateAntiClockwise2
	}
	enum Direction:CaseIterable {
	case right,down,left,up
	}
	//이미 방문한 곳을 방향별로 저장
	var dontMove:[Direction:[[Bool]]] = [:]
	//시계 방향 회전시 맨하튼거리
	let clockManhattan:[Direction:(Int,Int)] = [.up:(-1,-1),.down:(+1,+1),.left:(-1,+1),.right:(+1,-1)]
	//반시계 방향 회전시 맨하튼거리
	let antiClockManhattan:[Direction:(Int,Int)] = [.up:(+1,-1),.down:(-1,+1),.left:(-1,-1),.right:(+1,+1)]
	//방향에 따른 두번째 로봇 위치
	let directionXY:[Direction:(Int,Int)] = [.up:(0,-1),.down:(0,+1),.left:(-1,0),.right:(+1,0)]
	func solution(_ board:[[Int]]) -> Int {
	Direction.allCases.forEach{
	dontMove[$0] = Array(repeating: Array(repeating: false, count: board.count), count: board.count)
	}
	return findMinCountByBFS(board: board)
	}
	func findMinCountByBFS(board:[[Int]]) -> Int {
	let allCommand = Command.allCases
	var queue:[Current] = [Current(x: 0, y: 0, d: .right, count: 0, past: .right)]
	while !queue.isEmpty {
	var first = queue.removeFirst()
	let second = current2(current: first)
	if isEnabled(current: first, b: board) {
	if (first.x == board.count-1 && first.y == board.count-1) || (second.x == board.count-1 && second.y == board.count-1){
	return first.count
	}
	//방문 표시
	dontMove[first.d]![first.y][first.x] = true
	//카운트 1증가
	first.count += 1
	//명령별로 움직여줌
	for command in allCommand {
	var newCurrent = move(current: first, command: command)
	newCurrent.past = command
	queue.append(newCurrent)
	}
	}
	}
	return 0
	}
	//명령에 따라 움직인 위치를 반환
	func move(current:Current,command:Command) -> Current {
	var newCurrent = current
	let allDirection = Direction.allCases
	let index = allDirection.firstIndex(of: current.d) ?? -1
	switch command {
	case .up:
	newCurrent.y -= 1
	case .down:
	newCurrent.y += 1
	case .left:
	newCurrent.x -= 1
	case .right:
	newCurrent.x += 1
	case .rotateClockwise:
	newCurrent.d = index == 3 ? .right:allDirection[index+1]
	case .rotateAntiClockwise:
	newCurrent.d = index == 0 ? .up:allDirection[index-1]
	case .rotateClockwise2:
	newCurrent = current2(current: current)
	newCurrent.d = index == 0 ? .up :allDirection[index-1]
	case .rotateAntiClockwise2:
	newCurrent = current2(current: current)
	newCurrent.d = index == 3 ? .right :allDirection[index+1]
	}
	return newCurrent
	}
	//이동한 위치가 가능한 위치인지 확인
	func isEnabled(current:Current,b:[[Int]]) -> Bool {
	let second = current2(current: current)
	//현재 로봇이 지도 내에 있는지 확인
	if 0..<b.count ~= current.x && 0..<b.count ~= current.y && 0..<b.count ~= second.x && 0..<b.count ~= second.y {
	//현재 로봇이 있는 곳이 모두 0인지 확인
	if b[current.y][current.x] == 0 && b[second.y][second.x] == 0 {
	//현재 로봇이 있는 곳이 이미 지나간 곳이 아닌지 확인
	if !dontMove[current.d]![current.y][current.x] {
	//시계방향으로 회전했을 경우 각 현재 위치 맨하튼 거리가 0인지 확인
	if current.past == .rotateClockwise || current.past == .rotateClockwise2{
	return b[current.y+clockManhattan[current.d]!.1][current.x+clockManhattan[current.d]!.0] == 0
	//반시계방향으로 회전했을 경우 각 현재 위치 맨하튼 거리가 0인지 확인
	}else if current.past == .rotateAntiClockwise || current.past == .rotateAntiClockwise2{
	return b[current.y+antiClockManhattan[current.d]!.1][current.x+antiClockManhattan[current.d]!.0] == 0
	}else {
	return true
	}
	}
	}
	}
	return false
	}
	//방향에 따라 두번째 로봇 위치 반환
	func current2(current:Current) -> Current {
	var newCurrent = current
	newCurrent.x += directionXY[current.d]!.0
	newCurrent.y += directionXY[current.d]!.1
	return newCurrent
	}

view raw 블록 이동하기.swift hosted with ❤ by GitHub

---

후기

 

이번 문제는 한 3일동안 풀었던 문제다...

 

문제를 보자마자 BFS로 풀면 금방 풀리겠네? 하고 풀었는데

 

구현과정에서 이렇게 어려움을 겪은건 처음이었다..

 

처음엔 x1,y1,x2,y2로 설정해놓고 로봇을 움직이려하니 회전에 따라 코드 구현이 엄청 복잡해지고 하나라도

 

놓치면 어디서 틀렸는지 확인하는 시간이 오래걸렸다.. 처음부터 방향으로 설정했다면 금방 풀었을텐데..

 

또한 테스트케이스 1번이 계속 틀려서 왜 틀리는지 어떤 케이스인지 확인하려는 과정이 오래 걸렸다...

 

결국 알아냈는데 테스트케이스 1번은 로봇이 지도 맨 끝에 도착했을 때 가능한 위치에 있는지 없는지 확인해야했다.

 

ex)

 

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 r1 r2

0 0 0 1 0

 

아래와 같이 로봇이 있다면 마지막에 아래로 이동한 경우 가장 맨 끝에 이동할 수 있다.

 

하지만 r1에 1이 있으므로 도착했다 하더라도 가능한지 여부를 파악해야한다.