[코드트리] 2개의 사탕 (삼성 SW 역량테스트 2015 하반기 2번 문제)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/two-candies

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

 

2개의 사탕 문제 풀이는 BOJ 13460 : 구슬 탈출 2와 같다.

#include <stdio.h>

#define MAX (10 + 5)

int T;
int N, M;
char MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}CANDY;

CANDY red;
CANDY blue;

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

int minAnswer;

void input(void)
{
	minAnswer = 0x7FFF0000;

	scanf("%d %d", &N, &M);

	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < M; c++)
		{
			scanf(" %c", &MAP[r][c]);
			if (MAP[r][c] == 'R')
			{
				red.r = r;
				red.c = c;
			}

			if (MAP[r][c] == 'B')
			{
				blue.r = r;
				blue.c = c;
			}
		}
	}
}

void DFS(int L, int redR, int redC, int blueR, int blueC)
{
	if (L > 10) return;

	for (int i = 0; i < 4; i++)
	{
		int hole = 0;
		int nr, nc, mr, mc;
		nr = redR; nc = redC; mr = blueR; mc = blueC;

		while (1)
		{
			if (MAP[nr + dr[i]][nc + dc[i]] != '#' && MAP[mr + dr[i]][mc + dc[i]] != '#')
			{
				nr += dr[i]; nc += dc[i];
				mr += dr[i]; mc += dc[i];

				if (MAP[nr][nc] == 'O')
				{
					int flag = 0;
					while (MAP[mr][mc] != '#')
					{
						if (MAP[mr][mc] == 'O')
						{
							flag = 1;
							break;
						}
						mr += dr[i];
						mc += dc[i];
					}

					if (flag) break;
					else
					{
						if (minAnswer > L) minAnswer = L;
						return;
					}
				}

				if (MAP[mr][mc] == 'O')
				{
					hole = 1;
					break;
				}
			}
			else if (MAP[nr + dr[i]][nc + dc[i]] == '#'
				&& (MAP[mr + dr[i]][mc + dc[i]] != '#' && !(mr + dr[i] == nr && mc + dc[i] == nc)))
			{
				mr += dr[i];
				mc += dc[i];

				if (MAP[mr][mc] == 'O')
				{
					hole = 1;
					break;
				}
			}
			else if (MAP[mr + dr[i]][mc + dc[i]] == '#'
				&& (MAP[nr + dr[i]][nc + dc[i]] != '#' && !(nr + dr[i] == mr && nc + dc[i] == mc)))
			{
				nr += dr[i];
				nc += dc[i];

				if (MAP[nr][nc] == 'O')
				{
					if (minAnswer > L) minAnswer = L;
					return;
				}
			}
			else break;
		}

		if (hole == 0) DFS(L + 1, nr, nc, mr, mc);
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		DFS(1, red.r, red.c, blue.r, blue.c);

		if (minAnswer == 0x7FFF0000) printf("-1\n");
		else printf("%d\n", minAnswer);
	}

	return 0;
}