[C++] 백준 1726번: 로봇

문제 링크

백준 1726번: 로봇

문제 요약

0과 1로 이루어진 공장이 주어진다. 로봇은 0으로만 된 지점만 이동할 수 있다. 이 공장에서 로봇이 이동하는데, 출발 위치와 로봇이 보고 있는 방향, 도착 위치와 로봇이 보고 있는 방향이 주어진다. 이 때 로봇에게 다음 2개의 명령을 내려 목표에 도달하도록 하기 위한 최소 횟수를 구해야 한다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

접근 방법

보자마자 엄청 쉬운 BFS 문제일거라고 생각했지만 살짝 헤맸습니다. 일단 방향으로 주어지는 숫자 1, 2, 3, 4가 실제 방향 순서가 아니라 동서남북 순이라는 점을 TC를 넣고 디버깅하다가 알아차려서 혼란스러웠습니다.

일반 BFS처럼 작성을 하되, 방향도 함께 저장을 해줘야 합니다. 따라서 visited 배열같은 경우에도 3차원으로 선언을 해줄 필요가 있습니다. BFS 내에서는 2가지 명령에 대응되는 경우를 체크해줘야 합니다.

• 명령 1 : for문으로 1부터 3까지 현재 방향을 곱한다. 체크 후에 큐에 push한다.
• 명령 2 : 방향이 1 또는 2인 경우, 방향을 3과 4로 바꾼다. 방향이 3 또는 4인 경우, 방향을 1과 2로 바꾼다. 체크 후에 큐에 push한다.

명령 1의 경우, 1칸을 갔을 때 그 곳이 1이거나 구역을 벗어난다면, 그보다 앞으로 더 이동할 수는 없습니다. 따라서 갈 수 있는지 체크해주는 함수를 만들고, 반환형을 불리언형으로 둔 다음에 false값이 반환된다면 for문을 break 해주었습니다.

단, 이때 사용하는 체크 함수에서, 재방문을 체크하는 visited 배열의 값은 갈 수 있는지 없는지 여부와는 독립됩니다. 보통 이런 문제에서 BFS를 작성할 때는 행, 열의 범위, 가고자하는 칸의 값, visited(재방문 여부)값을 묶어서 if문을 작성하는데, 이런식으로 작성했다가 WA를 받았었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Info {
	int r, c, d, cnt;
};

int m, n, b[101][101], dir[5][2] = { {0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
bool visited[101][101][5];
Info s, e;

bool func(queue<Info>& q, Info next)
{
	if (next.r >= 1 && next.r <= m && next.c >= 1 && next.c <= n && !b[next.r][next.c])
	{
		if (!visited[next.r][next.c][next.d])
		{
			q.push(next);
			visited[next.r][next.c][next.d] = true;
		}
		return true;
	}
	else
		return false;
}

int bfs(void)
{
	queue<Info> q;
	q.push(s);
	visited[s.r][s.c][s.d] = true;
	s.cnt = 0;

	while (!q.empty())
	{
		Info now = q.front();
		q.pop();

		if (now.r == e.r && now.c == e.c && now.d == e.d)
			return now.cnt;

		for (int i = 1; i <= 3; i++)
		{
			Info next = { now.r + dir[now.d][0] * i, now.c + dir[now.d][1] * i, now.d, now.cnt + 1 };
			if (!func(q, next))
				break;
		}

		Info next = now;
		next.cnt++;
		
		if (now.d <= 2)
		{
			for (int i = 3; i <= 4; i++)
			{
				next.d = i;
				func(q, next);
			}
		}
		else
		{
			for (int i = 1; i <= 2; i++)
			{
				next.d = i;
				func(q, next);
			}
		}
	}

	return 0;
}

int main(void)
{
	cin >> m >> n;
	
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> b[i][j];

	cin >> s.r >> s.c >> s.d >> e.r >> e.c >> e.d;
	cout << bfs();
	return 0;
}