백준 1726 c++ "로봇" -PlusUltraCode-

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

[필자 사고]

처음에 DFS로 모든 경우의 수를 고려해야 하나?? 생각했는데 

단순히 visited를 한차원 늘려 방향까지 기록하게되면 BFS로 충분히 풀 수 있었다.

이 문제에서 조심해야 될 부분은 i=1~i=3 까지 이동할 때 병이나 이동할수없는 구간을 만나게 되면 반드시 break을 해줘야한다.

예를들어 2에서 벽이 있는데 3에는벽이 없을경우 탐색을 한 경우로 쳐지게 된다.

사전에 차단해야 된다.

놓치기 쉬운 부분이니 조심하자.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. struct Node

Node 구조체는 로봇의 현재 상태를 표현한다.
구성 요소는 다음과 같다:

• sero: 세로 좌표 (행)
• garo: 가로 좌표 (열)
• dir: 현재 바라보는 방향 (1~4)
• count: 현재까지 수행한 명령 횟수

이 구조체는 BFS 탐색에서 큐에 저장되는 단위 상태(state) 역할을 한다.

---

2. turnRight(int dir)

현재 방향을 기준으로 오른쪽으로 90도 회전했을 때의 방향을 반환한다.
방향 번호는 다음과 같이 정의되어 있다:

• 1: 동
• 2: 서
• 3: 남
• 4: 북
  규칙에 따라 변환 결과는 다음과 같다:
• 동(1) → 남(3)
• 서(2) → 북(4)
• 남(3) → 서(2)
• 북(4) → 동(1)

즉, 오른쪽 회전의 결과를 반환하는 순수 함수이다.

---

3. turnLeft(int dir)

현재 방향을 기준으로 왼쪽으로 90도 회전했을 때의 방향을 반환한다.
규칙은 다음과 같다:

• 동(1) → 북(4)
• 서(2) → 남(3)
• 남(3) → 동(1)
• 북(4) → 서(2)

즉, 왼쪽 회전 결과를 계산해 반환한다.

---

4. isInside(int sero, int garo)

주어진 좌표 (sero, garo)가 공장 범위 안에 존재하는지 확인한다.
조건은 다음과 같다:

• 세로 좌표는 1 ≤ sero ≤ N
• 가로 좌표는 1 ≤ garo ≤ M
  이 조건을 만족하면 true, 아니면 false를 반환한다.
  이 함수는 경계 밖으로 나가지 않도록 하는 안전장치 역할을 한다.

---

5. main() 함수

프로그램의 전체 흐름을 제어한다.
주요 과정은 다음과 같이 단계별로 정리된다.

(1) 입력 처리

• N, M: 공장의 세로와 가로 크기 입력
• arr: 공장 지도 (0: 이동 가능, 1: 이동 불가)
• visited: [N+1][M+1][5] 3차원 방문 배열로, 같은 칸이라도 방향이 다르면 다른 상태로 처리한다.
• 출발점 (sy1, sx1, d1) 과 도착점 (sy2, sx2, d2) 입력

(2) BFS 초기화

• queue<Node>를 생성하여 시작 상태를 큐에 넣고, 방문 처리한다.
• 큐에는 (현재 세로, 가로, 방향, 명령 수)를 저장한다.

(3) BFS 탐색 루프

while (!myQueue.empty()) 문으로 BFS를 수행한다.
각 단계의 세부 동작은 다음과 같다.

a. 현재 상태 가져오기

• 큐의 front를 꺼내 현재 위치, 방향, 명령 수를 가져온다.
• 목표 지점과 방향이 일치하면 nowCount를 출력하고 종료한다.

b. 회전 명령 처리

• turnLeft()와 turnRight()로 회전 후 방향을 계산한다.
• 아직 방문하지 않은 방향 상태라면 큐에 추가하고, 명령 수를 +1 한다.

c. 전진 명령(Go k) 처리

• 현재 방향으로 1칸, 2칸, 3칸씩 이동을 시도한다.
• 이동 중 다음과 같은 조건을 검사한다:
  1. isInside()로 범위 밖이면 즉시 중단 (break)
  2. arr[ns][ng] == 1이면 벽이므로 더 이상 이동 불가 (break)
  3. 이미 같은 방향으로 방문한 곳은 건너뜀 (continue)
• 위 조건을 모두 통과하면 새로운 상태를 큐에 추가한다.
• 이때 명령 횟수를 1 증가시킨다.

(4) 종료

BFS가 끝나면, 목적지에 도달했을 때의 최소 명령 횟수가 출력된다.

---

6. 동작 요약

1. 출발점에서 시작하여, 각 상태 (위치, 방향)을 BFS로 탐색한다.
2. 각 상태에서 가능한 모든 명령(Go 1~3, Turn left/right)을 시도한다.
3. 최소 명령 횟수를 구하기 위해 BFS를 사용하여 가장 먼저 목표 상태에 도달한 시점의 count를 출력한다.
4. 방향 전환과 이동은 모두 독립적인 상태로 간주하여 중복 탐색을 방지한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
	int sero;
	int garo;
	int dir;
	int count;
};

int dy[5] = { 0,0,0,1,-1 };
int dx[5] = { 0,1,-1,0,0 };

int N, M;
vector<vector<int>> arr;
vector<vector<vector<bool>>> visited;

int sy1, sx1, d1;
int sy2, sx2, d2;
//동 서 남 북
int turnRight(int dir) {
	if (dir == 1)return 3;
	if (dir == 2)return 4;
	if (dir == 3)return 2;
	if (dir == 4) return 1;
}

int turnLeft(int dir) {
	if (dir == 1)return 4;
	if (dir == 2) return 3;
	if (dir == 3) return 1;
	if (dir == 4) return 2;
}

bool isInside(int sero, int garo) {
	if (sero >= 1 && sero <= N && garo >= 1 && garo <= M)return true;
	return false;
}

int main(void) {
	cin >> N >> M;
	arr.assign(N + 1, vector<int>(M + 1, 0));
	visited.assign(N + 1, vector<vector<bool>>(M + 1, vector<bool>(5, false)));

	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= M; k++) {
			cin >> arr[i][k];
		}
	}

	cin >> sy1 >> sx1 >> d1;
	cin >> sy2 >> sx2 >> d2;
	
	queue<Node> myQueue;
	myQueue.push({ sy1,sx1,d1 ,0});
	visited[sy1][sx1][d1] = true;
	while (!myQueue.empty()) {
		int s = myQueue.front().sero;
		int g = myQueue.front().garo;
		int d = myQueue.front().dir;
		int nowCount = myQueue.front().count;

		if (s == sy2 && g == sx2 && d == d2) {
			cout << nowCount;
			return 0;
		}
		myQueue.pop();

		int nextLeftDir = turnLeft(d);
		int nextRightDir = turnRight(d);
		if (!visited[s][g][nextLeftDir]) {
			myQueue.push({ s,g,nextLeftDir,nowCount + 1 });
			visited[s][g][nextLeftDir] = true;
		}
		if (!visited[s][g][nextRightDir]) {
			myQueue.push({ s,g,nextRightDir,nowCount + 1 });
			visited[s][g][nextRightDir] = true;
		}

		for (int i = 1; i <= 3; i++) {
			int ns = s + dy[d] * i;
			int ng = g + dx[d] * i;

			if (!isInside(ns, ng)) break;      
			if (arr[ns][ng] == 1) break;       
			if (visited[ns][ng][d]) continue;  

			visited[ns][ng][d] = true;
			myQueue.push({ ns, ng, d, nowCount + 1 });
		}
	}
}