[BOJ 17500] 국경 C++ 풀이

문제 링크

www.acmicpc.net/problem/17500

17500번: 국경

이번 문제는 지문이 긴 관계로, 문제 내용은 생략하겠습니다.

풀이

이번 문제는 가능한 답이 여러 개일 수 있는 구현 문제였습니다.

지문에서, "위 조건을 만족하는 국경"을 그리라는 명시가 있기 때문에, 예제 출력과 나의 제출이 반드시 같아야 할 필요는 없습니다.

 

1. 문제접근

N이 최대 4까지 이므로, 가능한 경로를 중복 없이 전부 체크하면 가능한 문제였습니다.

저는 문제에 접근할 때, 1) N*N크기를 갖는 동물의 위치를 표시하는 행렬 , 2) N+1*N+1 크기를 갖는 국경의 꼭짓점을 표시하는 행렬을 통해, 동물과 국경의 위치를 나타내고자 했습니다.

 

깊이 우선 탐색(DFS)을 통해 국경 행렬에서, (0,0) 출발~(N, N) 도착이 가능한 모든 국경을 만들고,

너비 우선 탐색(BFS)을 통해 배치된 국경에 다른 종류의 동물 있는지를 검사했습니다.

 

BFS에서, 같은 국경 내에 다른 동물이 있는 경우가 있다면, 다른 국경으로 넘어갑니다.

반대로, 같은 국경 내에 같은 동물만 있다면, 그것은 답이므로 출력 후 프로그램을 종료합니다.

 

2. 코드 진행

1. 입력받기

2. DFS함수 solve(y, x) 호출

　　1) y==N && x==N인가? ( = (0,0) 출발, (N, N)도착인가?)

　　　　참)　isPossible() 호출, 같은 국경 내에 같은 동물만 있는지 확인

　　　　　　참) ㄱ. makeMap() 호출, 입출력 형식 맞춤

 　　　　　　　 ㄴ. printAns() 호출, 출력 형식 외곽에 #채우고 출력

　　　　　　　  ㄷ. 프로세스 종료

　　　　　　거짓) 2.로 돌아가 국경 생성　　　

　　　　거짓) 2.로 돌아가 국경 생성

 

소스코드

 

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int N;
char mat[4][4];
bool check[5][5];
int zone[4][4];
bool zonecheck[4][4];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
// 하 상 우 좌

int switchmat[5][5][2] = {
	{{0,0},{0,4},{0,8},{0,12},{0,16}},
	{{2,0},{2,4},{2,8},{2,12},{2,16}},
	{{4,0},{4,4},{4,8},{4,12},{4,16}},
	{{6,0},{6,4},{6,8},{6,12},{6,16}},
	{{8,0},{8,4},{8,8},{8,12},{8,16}}};

int switch_animal_mat[4][4][2] = {
	{{1,2},{1,6},{1,10},{1,14}},
	{{3,2},{3,6},{3,10},{3,14}}, 
	{{5,2},{5,6},{5,10},{5,14}}, 
	{{7,2},{7,6},{7,10},{7,14}} };

char printmat[9][18]={
	"+   +   +   +   +",
	"  .   .   .   .  ",
	"+   +   +   +   +",
	"  .   .   .   .  ",
	"+   +   +   +   +",
	"  .   .   .   .  ",
	"+   +   +   +   +",
	"  .   .   .   .  ",
	"+   +   +   +   +"};
/*
	경로는 좌상단시작 우하단끝
*/


void init()
{
	scanf(" %d", &N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			scanf(" %c", &mat[i][j]);
			int x = switch_animal_mat[i][j][1];
			int y = switch_animal_mat[i][j][0];
			printmat[y][x] = mat[i][j];
		}

	return;
}

bool makeZone(int starty, int startx,int zone_idx)
{
	zone[starty][startx] = zone_idx;
	zonecheck[starty][startx] = true;
	queue<pair<int, int>> q;
	q.push({ starty,startx });
	char animal = mat[starty][startx];
	while (!q.empty())
	{
		int x = q.front().second;
		int y = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (zonecheck[ny][nx])
				continue;

			zonecheck[ny][nx] = true;

			int nnx = switch_animal_mat[y][x][1];
			int nny = switch_animal_mat[y][x][0];
			int nnnx = switch_animal_mat[ny][nx][1];
			int nnny = switch_animal_mat[ny][nx][0];

			if (printmat[(nny + nnny) / 2][(nnx + nnnx) / 2] == ' ')
			{
				q.push({ ny,nx });
				zone[ny][nx] = zone_idx;

				if (animal == '.' && mat[ny][nx] != '.')
					animal = mat[ny][nx];
				else if (animal != '.' && mat[ny][nx] != '.' && animal != mat[ny][nx])
					return false;
			}
		}
	}

	return true;
}

bool isPossible()
{
	memset(zone, 0, sizeof(zone));

	int zone_idx = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (zone[i][j] == 0)
			{
				memset(zonecheck, 0, sizeof(zonecheck));
				if (!makeZone(i, j, zone_idx++))
					return false;
					
			}
		}
	}

	return true;
}

void makeMap()
{
	for (int i = 0; i < 5; i++)
	{
		int nny = switchmat[i][0][0];
		for (int j = 0; j < 4; j++)
		{
			int nnx = switchmat[i][j][1];
			int nnnx = switchmat[i][j+1][1];
			int nnnnx = (nnx + nnnx) / 2;
			if (printmat[nny][nnnnx] == '-')
			{
				printmat[nny][nnnnx - 1] = '-';
				printmat[nny][nnnnx + 1] = '-';
			}
		}
	}
	return;
}

void printAns()
{
	printf("yes\n");
	for (int i = 0; i < N * 2 + 3; i++)
	{
		for (int j = 0; j < N * 4 + 3; j++)
		{
			if (i == 0 || i == N * 2 + 2)
				printf("#");
			else
			{
				if (j == 0 || j == N * 4 + 2)
					printf("#");
				else
				{
					printf("%c", printmat[i - 1][j - 1]);
				}
			}
		}
		printf("\n");
	}
	return;
}

void solve(int starty, int startx)
{
	if (starty == N && startx == N)
	{
		if (isPossible())
		{
			makeMap();
			printAns();
			exit(0);
		}
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int ny = starty + dy[i];
		int nx = startx + dx[i];

		if (nx < 0 || nx >= N + 1 || ny < 0 || ny >= N + 1)
			continue;
		if (check[ny][nx])
			continue;

		check[ny][nx] = true;
		char map_symbol = i < 2 ? '|' : '-';
		int nny = switchmat[starty][startx][0];
		int nnx = switchmat[starty][startx][1];
		int nnny = switchmat[ny][nx][0];
		int nnnx = switchmat[ny][nx][1];

		printmat[(nny+nnny)/2][ (nnx+nnnx)/2] = map_symbol;
		solve(ny, nx);
		check[ny][nx] = false;
		printmat[(nny + nnny) / 2][(nnx + nnnx) / 2] = ' ';
	}

	return;
}


int main()
{

	init();

	check[0][0] = true;
	solve(0,0);

	printf("no\n");
	return 0;

	/*
		N이 최대 4밖에 안되니까 중복없이 다돌리면될듯.
		DFS로 0,0~4,4를 관통하는 루트를 짜고
		bfs로 존을 편성한 후에
		존과 비교해서 가능하면 printAns하고 끝
		
		아니면 계속하다가
		마지막에 no
	*/

}

1. 예제 1 결과

2. 예제 2 결과

3. 예제 3 결과

예제 3은 예제 출력과 다르지만, 조건을 만족하므로 정답입니다.

4. 예제 4 결과

예제 4는 예제 출력과 다르지만, 조건을 만족하므로 정답입니다.

5. 예제 5 결과

 

질문과 잘못된 정보 수정 요청은 언제나 환영합니다. 편하게 댓글을 달아주세요.

오늘도 부족한 제 글을 읽어주셔서 감사합니다.