-
JUNGOL/Intermediate_Coder/그래프탐색-BFS/1006 : 로봇코딩 테스트/JUNGOL 2023. 3. 1. 15:36
Intermediate_Coder/그래프탐색-BFS/로봇
문제
많은 공장에서 로봇이 이용되고 있다.
우리 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며 움직이는 방향은 동, 서, 남, 북 가운데 하나이다.
로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.
*명령 1. Go k
- k 는 1 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k 칸만큼 움직인다.*명령 2. Turn dir
- dir 은 left 또는 right 이며 각각 왼쪽 또는 오른쪽으로 90° 회전한다.공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다.
0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고 1은 궤도가 없어 로봇이 갈 수 없는 지점이다.
로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때
이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.
JUNGOL 그래프탐색-BFS 로봇 로봇의 현재 위치와 바라보는 방향이 주어졌을 때 로봇을 원하는 위치로 이동시키고 원하는 방향으로 바라보도록 하는데
최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다.
이 때 M과 N은 둘 다 100이하의 자연수이다.
이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다.
다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.
마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.
방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.
출력 형식
첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.
입력 예
5 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 0 0 0 0
0 0 1 1 1 0
1 0 0 0 0 0
4 2 3
2 4 1출력 예
9
RobotToMove.h
#pragma once #include <iostream> #include <queue> #include "../../Base.h" using std::queue; class RobotToMove : public Base { protected: struct Direction { int x, y; }; struct Position { int x, y; int cost; int direction; Position() : x(0), y(0), cost(0), direction(0) {} int GetTurnCost(int dir) { int cost = 1; // 같은 방향은 코스트가 들지 않는다. if (direction == dir) { cost = 0; } // 반대 방향은 두 번 돌아야 하므로 비용이 2가 된다. else if (direction == 0 && dir == 1 || direction == 1 && dir == 0 || direction == 2 && dir == 3 || direction == 3 && dir == 2) { cost = 2; } return cost; } }; public: virtual void Code() override; private: int GetLeastCostToGo(); bool IsArrive(const Position& p) const; bool CanMoveTo(const Position& p) const; bool IsInMap(const Position& p) const; private: const Direction directionToMove[4]{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int m, n; bool map[101][101]{}; bool visited[101][101][4]{}; queue<Position> q; Position start, end; };RobotToMove.cpp
void RobotToMove::Code() { std::cin >> m >> n; int inVal; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { std::cin >> inVal; map[i][j] = (inVal == 0); } } std::cin >> start.y >> start.x >> start.direction; std::cin >> end.y >> end.x >> end.direction; // 0 부터 시작할 수 있도록 보정 start.y--; start.x--; start.direction--; end.y--; end.x--; end.direction--; std::cout << GetLeastCostToGo(); } /// <summary> /// 이동하는데 필요한 최소 명령 횟수를 반환한다. /// </summary> /// <returns>최소 명령 횟수</returns> int RobotToMove::GetLeastCostToGo() { int leastCost = 999'999'999; visited[start.y][start.x][start.direction] = true; q.push(start); while (q.empty() == false) { Position p = q.front(); q.pop(); if (IsArrive(p)) { leastCost = p.cost; break; } // 주어진 방향으로 이동을 시도한다. for (int i = 1; i <= 3; i++) { Position newP{ p }; newP.x += directionToMove[newP.direction].x * i; newP.y += directionToMove[newP.direction].y * i; newP.cost++; // 방문한 적 있는 방향은 무시한다. if (visited[newP.y][newP.x][p.direction]) { continue; } if (CanMoveTo(newP) == false) { break; } visited[newP.y][newP.x][newP.direction] = true; q.push(newP); } // 현재 위치에서 회전을 체크한다. for (int i = 0; i < 4; i++) { // 위치, 방향이 체크된 적 있으면 무시한다. if (visited[p.y][p.x][i]) { continue; } Position newP{ p }; newP.direction = i; newP.cost += p.GetTurnCost(i); visited[newP.y][newP.x][i] = true; q.push(newP); } } return leastCost; } /// <summary> /// 도착 했는지 여부를 반환한다. /// </summary> /// <param name="p">확인할 지점</param> /// <returns>도착 여부</returns> bool RobotToMove::IsArrive(const Position& p) const { return p.x == end.x && p.y == end.y && p.direction == end.direction; } /// <summary> /// 새로운 위치로 이동할 수 있는지 여부를 반환한다. /// </summary> /// <param name="p">확인할 지점</param> /// <returns>이동 가능한지 여부</returns> bool RobotToMove::CanMoveTo(const Position& p) const { if (IsInMap(p) == false) { return false; } return map[p.y][p.x]; } /// <summary> /// 새로운 위치가 맵 안에 들어가는지 여부를 반환한다. /// </summary> /// <param name="p">확인할 지점</param> /// <returns>맵 안에 있는지 여부</returns> bool RobotToMove::IsInMap(const Position& p) const { if (p.x < 0) return false; if (p.x >= n) return false; if (p.y < 0) return false; if (p.y >= m) return false; return true; }
실행 결과 Success(100)
코드 해설
이 문제에서 비용이 발생하는 경우는 다음과 같다.
- 1칸 ~ 3칸 이동 시
- 방향 90도 전환 시
방향 전환의 경우 90도 씩 나눠서 처리할 수도 있으나 단순하게 같은 방향이면 비용을 0으로 적용하고, 180도 회전이면 비용을 두 배로 적용하는 식으로 처리할 수도 있다.
int GetTurnCost(int dir) { int cost = 1; // 같은 방향은 코스트가 들지 않는다. if (direction == dir) { cost = 0; } // 반대 방향은 두 번 돌아야 하므로 비용이 2가 된다. else if (direction == 0 && dir == 1 || direction == 1 && dir == 0 || direction == 2 && dir == 3 || direction == 3 && dir == 2) { cost = 2; } return cost; }방문 체크의 경우 회전과 이동이 각각 따로 진행되기 때문에 방향을 함께 확인해야 했다.
bool visited[101][101][4]{};이동 시에는 회전으로 해당 위치에 방문했다고 체크된 경우가 있을 수 있으므로 해당 지점에 이동이 불가능 하다고 하더라도 다음 위치(1칸 ~ 3칸이므로) 체크를 진행해야 한다.
// 주어진 방향으로 이동을 시도한다. for (int i = 1; i <= 3; i++) { Position newP{ p }; newP.x += directionToMove[newP.direction].x * i; newP.y += directionToMove[newP.direction].y * i; newP.cost++; // 방문한 적 있는 방향은 무시한다. if (visited[newP.y][newP.x][p.direction]) { continue; } if (CanMoveTo(newP) == false) { break; } visited[newP.y][newP.x][newP.direction] = true; q.push(newP); }
회전 체크도 마찬가지로 이동을 통해 해당 방향이 사용 되었을 수 있으므로 먼저 사용된 방향을 체크해 줘야 한다.// 현재 위치에서 회전을 체크한다. for (int i = 0; i < 4; i++) { // 위치, 방향이 체크된 적 있으면 무시한다. if (visited[p.y][p.x][i]) { continue; } Position newP{ p }; newP.direction = i; newP.cost += p.GetTurnCost(i); visited[newP.y][newP.x][i] = true; q.push(newP); }NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)
NadanKim/CodingTest_JUNGOL
JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.
github.com