백준 1726 : 로봇 c++

www.acmicpc.net/problem/1726

1726번: 로봇

 

풀이겸 후기

 

1. 다른 BFS랑 다르게 추가로 생각해야되는 부분이 쫌 많았다

1) 그냥 기존 깊이에따라 cnt 할때랑 다르게 방향전환 을 고려해야되서 평소의 4방향 좌표 변환 전에 cnt를 미리 정해두는 방식을 쓸 수 없었다

-> struct로 묶어서 queue에 삽입

 

2) 각 좌표별로 바라보는 방향에 따른 visited 배열을 관리해야됬다

-> int visited[100][100][5];

 

3) 여러방향에서 하나의 칸으로 올 수 도 있어서 visited를 0과 1이 아닌 크기로 비교

 

처음에는 방향전환을 한번해서 여기로 온다면 기존 cnt에 +2 이므로

기존 cnt 값이 이보다 작으면 굳이 안해도 된다고 생각했다.

 

4) 사실 그냥 동서남북으로 다 탐색하는걸 어거지로 해버려서 이렇게 고생한거지 

 그냥 정석은 1칸, 2칸, 3칸 전진 , 왼쪽 방향전환, 오른쪽 방향전환 이렇게 5가지경우 BFS 하면 된다....

 

 

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

struct robot {
	int r, c, way, cnt;
};

int d_r[5] = { 0,0,0,1,-1 }; // 동 서 남 북
int d_c[5] = { 0,1,-1,0,0 };// 동서남북 0번은 안씀

int m, n;
robot start;
robot robot_end;
queue<robot>q;
int map[100][100];
int visited[100][100][5];
int answer = 987654321;

void bfs()
{
	while (!q.empty())
	{
		robot now = q.front();
		q.pop();


		if (now.r == robot_end.r && now.c == robot_end.c)//최종 목적지에 도달했으면
		{
			int sum = now.cnt;
			if (robot_end.way == now.way)
				sum = sum;
			else if (robot_end.way == 1 && now.way == 2)
				sum = sum + 2;
			else if (robot_end.way == 2 && now.way == 1)
				sum = sum + 2;
			else if (robot_end.way == 3 && now.way == 4)
				sum = sum + 2;
			else if (robot_end.way == 4 && now.way == 3)//반대방향이라면
				sum = sum + 2;
			else
				sum = sum + 1;
			answer = min(answer, sum);
		}

		for (int i = 1; i <= 4; i++)//가야되는 방향
		{
			for (int s = 1; s <= 3; s++)// 1 2 3 만큼 이동 가능
			{
				int new_r = now.r + d_r[i] * s;
				int new_c = now.c + d_c[i] * s;
				if (new_r <= 0 || new_c <= 0 || new_r > m || new_c > n)//지도 밖
					continue;

				if (map[new_r][new_c] == 1)//못가는길
					break;
				if (visited[new_r][new_c][i] != 0)//방문한적 잇으면
				{
					if(visited[new_r][new_c][i]<now.cnt+2)
						continue;
				}
				int cnt = now.cnt + 1;//이동이니까
				//원하는 쪽으로 가기 위한 방향 전환

				if (i == now.way)
					cnt = cnt;
				else if (i == 1 && now.way == 2)
					cnt = cnt + 2;
				else if (i == 2 && now.way == 1)
					cnt = cnt + 2;
				else if (i == 3 && now.way == 4)
					cnt = cnt + 2;
				else if (i == 4 && now.way == 3)//반대방향이라면
					cnt = cnt + 2;
				else
					cnt = cnt + 1;

				visited[new_r][new_c][i] = cnt;
				robot temp;
				temp.r = new_r;
				temp.c = new_c;
				temp.cnt = cnt;
				temp.way = i;
				q.push(temp);
			}
		}

	}

}
int main()
{
	cin >> m >> n;// 행 열
	memset(visited, 0, sizeof(visited));

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}

	cin >> start.r >> start.c >> start.way;
	start.cnt = 0;
	q.push(start);
	for(int i=1;i<=4;i++)
		visited[start.r][start.c][i] = 1;

	cin >> robot_end.r >> robot_end.c >> robot_end.way;

	bfs();

	cout << answer << endl;
	return 0;
}