삼성 A형 샘플 문제 : 프로세서 연결하기

 

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

 

삼성 A형 전체 링크

 

swexpertacademy.com/main/sst/intro.do

 

 

SW Expert Academy에서 A형 샘플 문제 프로세서 연결하기를 풀어보자. 

 

좌표는 (1, 1)부터 받고, 주변을 MAP[r][c] = 2(벽)으로 처리해서 경계 조건을 쉽게 처리하도록 하자.

(core = 1, 벽 = 2, 전선 = 3 으로 정의한다.)

#define MAX (10 + 5)

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

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 2;

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

 

tc가 여러 개이기 때문에 매 tc마다 input을 받고, 초기화를 해줘야 한다.

이 문제에서는 최대 core에서 최소 전선 개수인 MINANS와 FLAG(나중에 설명), core의 개수를 초기화 한다.

core 개수를 초기화한 후에는 MAP의 좌표에서 1인 값을 찾아 core의 좌표를 저장한다.

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

RC core[MAX*MAX]; /* core의 좌표 */
int ccnt; /* core의 개수 */

...

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

		/* init */
		ccnt = FLAG = 0;
		MINANS = 0x7fff0000;

		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c] == 1 && isBoundary(r, c) == 0)
				{
					core[ccnt].r = r;
					core[ccnt++].c = c;
				}
			}
		}

		/* DFS */

		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}

 

"멕시노스의 가장자리에 위치한 Core는 이미 전원이 연결된 것으로 간주한다." 조건에 의해

주변이 벽(MAP[r][c] = 2)인 경우는 개수를 세지도 않고, 좌표를 저장하지도 않는다.

isBoundary 함수를 이용해 4방향 중 벽이 하나라도 있다면, return 1을 하여 init에서 core 배열에 담지 않도록 한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int isBoundary(int r, int c)
{
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = r + dr[i];
		nc = c + dc[i];

		if (MAP[nr][nc] == 2) return 1;
	}

	return 0;
}

---

아래의 조건을 만족하도록 DFS 실행 방법을 고민해보자.

 

▶ 최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.
   단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.

 

CORE의 최대 개수 = 12, 연결 방향 4방향 + 연결하지 않음 = 5이므로,

모든 core를 연결하기에는 경우의 수가 꽤 많다. (5¹² = 244,140,625)

 

하지만 가장 많이 연결하는 경우를 찾아야하므로, core의 전선 연결 실패가 0인 경우를 먼저 찾아본다.

연결 실패가 0인 경우에서 답을 찾지 못하면 모든 core를 연결하지 않은 경우까지 1씩 가능한 실패 횟수를 늘린다.

이 때, DFS에서 연결이 가능하다고 판단되면 FLAG = 1로 변경해서, 더 이상 DFS를 실행하지 않는다.

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

		for (int fail = 0; fail < ccnt; fail++)
		{
			FAIL_COUNT = fail;
			DFS(0, 0, MAP);
			if (FLAG) break;
		}

		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}

 

DFS는 아래와 같이 구성된다.

 

1) 연결 실패 시, 다음 DFS에서 failCount를 증가한다. 이 failCount가 main에서 정한 FAIL_COUNT보다 크면 종료.

2) L == ccnt, 즉 모든 core를 다 연결하였고, FAIL_COUNT도 만족하면, 전선의 개수를 갱신한다.

3) 4방향으로 전선을 연결하는지 check하고, 가능하다면 전선을 set한다. DFS가 종료되면 delete한다.

4) 전선 연결이 불가능한 경우는 1)에서 설명한대로 count 증가 및 복사한 map을 그대로 넘긴다.

int FLAG, FAIL_COUNT;
int MINANS = 0x7fff0000;
void DFS(int L, int failCount, int map[MAX][MAX])
{
	/* 1) */
	if (failCount > FAIL_COUNT) return;
    
	/* 2) */
	if (L == ccnt)
	{
		if (failCount == FAIL_COUNT)
		{
			FLAG = 1;

			int tmp = countLink(map);
			if (MINANS > tmp) MINANS = tmp;		
		}

		return;
	}

	int tmpMAP[MAX][MAX] = { 0 };

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			tmpMAP[r][c] = map[r][c];

	for (int dir = 0; dir < 4; dir++)
	{
		/* 3) */
		if (checkLink(core[L].r, core[L].c, dir, tmpMAP))
		{
			setLink(core[L].r, core[L].c, dir, tmpMAP);
			DFS(L + 1, failCount, tmpMAP);
			deleteLink(core[L].r, core[L].c, dir, tmpMAP);
		}
	}
	
	/* 4) 전선을 연결하지 않은 경우, failCount 증가 */
	DFS(L + 1, failCount + 1, tmpMAP);
}

---

checkLink, setLink, deleteLink는 모두 비슷한 방식으로 만들어지고 동작만 다르다.

dr, dc 배열을 보고 벽(2)이 나올 때 까지, core(1)나 전선(3)이 없는지 체크한다.

없다면 전선을 설치할 수 있으므로, setLink로 전선을 설치(MAP[r][c] = 3)한다.

DFS 종료 후, 전선을 제거해야하므로 deleteLink로 MAP[r][c] = 0로 변경한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

...

int checkLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	if (dir == 4) return 1;

	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 1 || map[nr][nc] == 3) return 0;
		else if (map[nr][nc] == 2) return 1;
	}

	return -1; /* impossible case */
}

void setLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 2) return;

		map[nr][nc] = 3;
	}
}

void deleteLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 2) return;

		map[nr][nc] = 0;
	}
}

 

전선을 세는 함수는 더 간단하다. map[r][c]가 3인 좌표를 세면 된다.

int countLink(int map[MAX][MAX])
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (map[r][c] == 3) sum++;

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 5)

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

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

RC core[MAX*MAX];
int ccnt;

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = 2;

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

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int isBoundary(int r, int c)
{
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = r + dr[i];
		nc = c + dc[i];

		if (MAP[nr][nc] == 2) return 1;
	}

	return 0;
}

int checkLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	if (dir == 4) return 1;

	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 1 || map[nr][nc] == 3) return 0;
		else if (map[nr][nc] == 2) return 1;
	}

	return -1; /* impossible case */
}

void setLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 2) return;

		map[nr][nc] = 3;
	}
}

void deleteLink(int sr, int sc, int dir, int map[MAX][MAX])
{
	int nr, nc;

	nr = sr; nc = sc;
	while (1)
	{
		nr += dr[dir];
		nc += dc[dir];

		if (map[nr][nc] == 2) return;

		map[nr][nc] = 0;
	}
}

int countLink(int map[MAX][MAX])
{
	int sum = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (map[r][c] == 3) sum++;

	return sum;
}

int FLAG, FAIL_COUNT;
int MINANS = 0x7fff0000;
void DFS(int L, int failCount, int map[MAX][MAX])
{
	if (failCount > FAIL_COUNT) return;

	if (L == ccnt)
	{
		if (failCount == FAIL_COUNT)
		{
			FLAG = 1;

			int tmp = countLink(map);
			if (MINANS > tmp) MINANS = tmp;		
		}

		return;
	}

	int tmpMAP[MAX][MAX] = { 0 };

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			tmpMAP[r][c] = map[r][c];

	for (int dir = 0; dir < 4; dir++)
	{
		if (checkLink(core[L].r, core[L].c, dir, tmpMAP))
		{
			setLink(core[L].r, core[L].c, dir, tmpMAP);
			DFS(L + 1, failCount, tmpMAP);
			deleteLink(core[L].r, core[L].c, dir, tmpMAP);
		}
	}

	DFS(L + 1, failCount + 1, tmpMAP);
}

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

		ccnt = FLAG = 0;
		MINANS = 0x7fff0000;

		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c] == 1 && isBoundary(r, c) == 0)
				{
					core[ccnt].r = r;
					core[ccnt++].c = c;
				}
			}
		}

		for (int fail = 0; fail < ccnt; fail++)
		{
			FAIL_COUNT = fail;
			DFS(0, 0, MAP);
			if (FLAG) break;
		}

		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}