[코드트리] 자율주행 자동차 (삼성 SW 역량테스트 2017 상반기 오후 1번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/autonomous-driving

이후 설명 및 입/출력은 링크 참고

 

자율주행 자동차 문제 풀이는 BOJ 14503 : 로봇 청소기와 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M, R, C, D;
int MAP[MAX][MAX];

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

void input()
{
	scanf("%d %d %d %d %d", &N, &M, &R, &C, &D);

	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			MAP[r][c] = 0;

	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			scanf("%d", &MAP[r][c]);
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		int flag, sum;
		int change[] = { 3, 0, 1, 2 };

		input();

		flag = 0;
		while (1)
		{
			MAP[R][C] = 2; /* 1. 현재 위치를 청소한다. */

			/* 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. */

			int tmpDir = change[D]; /* 왼쪽을 탐색하기 위한 방향과 좌표 설정. */
			int nr = R + dr[tmpDir];
			int	nc = C + dc[tmpDir];

			/* a. 왼쪽 방향에 아직 가지 않은 공간이 존재한다면,
			그 방향으로 회전한 다음 한 칸을 전진하고 */
			if (MAP[nr][nc] == 0)
			{
				D = tmpDir;
				R = nr;
				C = nc;

				MAP[R][C] = 2; /* 1번부터 진행한다. */
			}
			else /* b. 왼쪽 방향으로 갈 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.*/
			{
				int i;
				for (i = 0; i < 4; i++)
				{
					// 회전
					D = tmpDir;
					//printf("%d\n", D);
					int nr = R + dr[D];
					int nc = C + dc[D];

					//회전한 방향이 청소할 수 있다면.
					if (MAP[nr][nc] == 0)
					{
						R = nr;
						C = nc;
						break;
					}

					tmpDir = change[D];
				}

				/* c. 네 방향 모두 갔던 도로거나 이미 되어있거나 벽인 경우에는,
				바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. */
				if (i == 4)
				{
					nr = R - dr[D]; /* 후진 */
					nc = C - dc[D];
					R = nr;
					C = nc;

					/* d. 네 방향 모두 이미 갔던 도로거나 벽이면서,
					뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. */
					if (MAP[R][C] == 1) flag = 1;
				}

			}

			if (flag) break;
		}

		MAP[R][C] = 5;

		sum = 0;
		for (int r = 0; r < N; r++)
			for (int c = 0; c < M; c++) /* 도로의 면적 count */
				if (MAP[r][c] == 2) sum++;

		printf("%d\n", sum);
	}
	
	return 0;
}