BOJ 19236 : 청소년 상어 (삼성 SW TEST A형)

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

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/1152 (A형 문제집)

www.acmicpc.net/problem/19236

아래와 같이 FISH 구조체를 선언하여 좌표와 방향, 그리고 죽었는지 살았는지 체크하는 dead를 정의하자.

상어의 이동을 쉽게 종료하기 위해 MAP 주변은 -1로 벽을 만들고, (1, 1)부터 입력을 받자.

MAP에는 물고기의 번호만 저장하고, 그 물고기 번호로 fish 배열에서 물고기의 정보를 찾는다.

int MAP[6][6];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int dead;
}FISH;

FISH Fish[17];

void input()
{
	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			MAP[r][c] = -1; /* 벽 표시 */

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			int number, dir;

			scanf("%d %d", &number, &dir);

			MAP[r][c] = number;
			
			Fish[number].r = r;
			Fish[number].c = c;
			Fish[number].dir = dir;
		}
	}	
}

이동을 위해 방향 1 ~ 8을 dr, dc 배열로 정의하고, 방향 변경을 위해 changeDir 배열을 만든다.

changeDir[1] = 2, changeDir[2] = 3, ..., changeDir[8] = 1, 이 되도록 선언하면 방향 변환이 편하다.

물론, 나머지 연산을 써도 되지만, 이 경우 방향을 0 ~ 7로 정의하는 것이 편하다.

int dr[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int changeDir[] = { 0, 2, 3, 4, 5, 6, 7, 8, 1 };

DFS는 상어의 좌표 sr, sc, 그리고 방향 dir, 누적할 점수 score, 그리고 map과 fish를 넘겨준다.

DFS의 종료 조건은 상어가 이동한 위치에 물고기가 없는 경우와, 벽에 부딪히는 경우가 된다.

벽에 부딪히는 경우에는 지금까지 잡은 물고기의 score를 MAXANS와 비교하여 갱신한다.

DFS 초기에는 map과 fish를 복사하고, 상어의 좌표에 죽은 물고기가 있으면 종료하는 코드를 넣는다.

void DFS(int sr, int sc, int dir, int score, int map[6][6], FISH fish[])
{
	int tmpMAP[6][6];
	FISH shark = { 0 };
	FISH tmpFish[17] = { 0 };

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

	for (int i = 1; i <= 16; i++) tmpFish[i] = fish[i];

	if (tmpFish[tmpMAP[sr][sc]].dead == 1) return; /* 물고기가 없는 경우 */
    
    ...   
}

물고기가 존재한다면 상어의 좌표를 갱신하고, 물고기의 방향을 상어의 방향으로 변경한다.

그리고 map에서 물고기의 번호를 찾아 score에 물고기의 번호를 더하고, 해당 물고기는 dead = 1로 표시한다.

void DFS(int sr, int sc, int dir, int score, int map[6][6], FISH fish[])
{
	...
    
    if (tmpFish[tmpMAP[sr][sc]].dead == 1) return; /* 물고기가 없는 경우 */

	shark.r = sr;
	shark.c = sc;

	int deadFishNumber = tmpMAP[sr][sc]; /* 상어에게 잡아 먹힌 물고기의 번호 */

	shark.dir = tmpFish[deadFishNumber].dir;
	
	score += deadFishNumber; /* 물고기 합 갱신 */
	tmpFish[deadFishNumber].dead = 1; /* 물고기 dead 표시 */
  
	...
}

상어가 물고기를 잡아먹었으므로 물고기를 순서대로 이동시킨다.

죽은 물고기는 이동시키지 않으므로 continue로 처리한다.

dr, dc 배열을 이용해 이동할 위치가 벽(-1)인지, 상어의 좌표와 같은지 체크하고, 그런 경우라면 방향을 변경한다.

그렇지 않다면, fish 배열의 물고기를 교환한다.

이때, 방향은 유지해야하므로, (r, c)만 직접 옮긴다. 마찬가지로 map에서도 물고기를 교환한다.

void DFS(int sr, int sc, int dir, int score, int map[6][6], FISH fish[])
{
	...

	for (int number = 1; number <= 16; number++)
	{	
		FISH f = tmpFish[number];
		
		if (f.dead) continue;

		while (1)
		{
			int nr, nc;
			
			nr = f.r + dr[f.dir];
			nc = f.c + dc[f.dir];
			
			if (tmpMAP[nr][nc] == -1 || (nr == shark.r && nc == shark.c))
			{
				tmpFish[number].dir = f.dir = changeDir[f.dir];
				continue;
			}
			else
			{
				int changeFishNumber = tmpMAP[nr][nc];

				int tmpR, tmpC;

				tmpR = tmpFish[number].r;
				tmpFish[number].r = tmpFish[changeFishNumber].r;
				tmpFish[changeFishNumber].r = tmpR;

				tmpC = tmpFish[number].c;
				tmpFish[number].c = tmpFish[changeFishNumber].c;
				tmpFish[changeFishNumber].c = tmpC;

				int tmp = tmpMAP[nr][nc];
				tmpMAP[nr][nc] = tmpMAP[f.r][f.c];
				tmpMAP[f.r][f.c] = tmp;

				break;
			}
		}
	}
 
 	...
    
}

이제 상어를 움직인다. 상어는 map의 모든 위치에서 최대 3칸까지 움직일 수 있다.

따라서 dr, dc 배열에 1 ~ 3까지 곱한 값을 현재 상어의 좌표에 더해야 한다.

다음 좌표가 벽이라면 상어는 집으로 돌아간다고 하였으므로, 현재까지 잡은 물고기를 MAXANS와 비교, 갱신한다.

그렇지 않다면 다음 DFS에 이동할 좌표와 현재 DFS의 score, map, fish를 넘겨주면 된다.

void DFS(int sr, int sc, int dir, int score, int map[6][6], FISH fish[])
{	
    ...
    
	for (int move = 1; move <= 3; move++)
	{
		int nr, nc;

		nr = shark.r + dr[shark.dir] * move;
		nc = shark.c + dc[shark.dir] * move;

		if (map[nr][nc] == -1)
		{
			if (MAXANS < score) MAXANS = score;
			break; /* 더 이상 움직일 수 없는 경우 종료 */
		}

		DFS(nr, nc, shark.dir, score, tmpMAP, tmpFish);
	}
}

최종 코드는 아래를 참고하자.

#include <stdio.h>

int MAP[6][6];

typedef struct st2
{
	int r;
	int c;
	int dir;
	int dead;
}FISH;

FISH Fish[17];

void input()
{
	for (int r = 0; r <= 5; r++)
		for (int c = 0; c <= 5; c++)
			MAP[r][c] = -1; /* 벽 표시 */

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			int number, dir;

			scanf("%d %d", &number, &dir);

			MAP[r][c] = number;
			
			Fish[number].r = r;
			Fish[number].c = c;
			Fish[number].dir = dir;
		}
	}	
}

void output(FISH shark, int map[6][6], FISH fish[], int score)
{
	printf("shark : r %d, c %d, dir %d score %d\n", shark.r, shark.c, shark.dir, score);
	printf("live : ");
	for (int i = 1; i <= 16; i++)
		if (fish[i].dead == 0) printf("%d, ", i);
	putchar('\n');

	for (int r = 1; r <= 4; r++)
	{
		for (int c = 1; c <= 4; c++)
		{
			if (r == shark.r && c == shark.c) printf("(%d, %d) ", -1, shark.dir);
			else printf("(%d, %d) ", map[r][c], fish[map[r][c]].dir);
			
		}
		putchar('\n');
	}
	putchar('\n');
}


int dr[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int changeDir[] = { 0, 2, 3, 4, 5, 6, 7, 8, 1 };

int MAXANS = 0;
void DFS(int sr, int sc, int dir, int score, int map[6][6], FISH fish[])
{
	int tmpMAP[6][6];
	FISH shark = { 0 };
	FISH tmpFish[17] = { 0 };

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

	for (int i = 1; i <= 16; i++) tmpFish[i] = fish[i];

	if (tmpFish[tmpMAP[sr][sc]].dead == 1) return; /* 물고기가 없는 경우 */

	shark.r = sr;
	shark.c = sc;

	int deadFishNumber = tmpMAP[sr][sc]; /* 상어에게 잡아 먹힌 물고기의 번호 */

	shark.dir = tmpFish[deadFishNumber].dir;
	
	score += deadFishNumber; /* 물고기 합 갱신 */
	tmpFish[deadFishNumber].dead = 1; /* 물고기 dead 표시 */
	
	for (int number = 1; number <= 16; number++)
	{	
		FISH f = tmpFish[number];
		
		if (f.dead) continue;

		while (1)
		{
			int nr, nc;
			
			nr = f.r + dr[f.dir];
			nc = f.c + dc[f.dir];
			
			if (tmpMAP[nr][nc] == -1 || (nr == shark.r && nc == shark.c))
			{
				tmpFish[number].dir = f.dir = changeDir[f.dir];
				continue;
			}
			else
			{
				int changeFishNumber = tmpMAP[nr][nc];

				int tmpR, tmpC;

				tmpR = tmpFish[number].r;
				tmpFish[number].r = tmpFish[changeFishNumber].r;
				tmpFish[changeFishNumber].r = tmpR;

				tmpC = tmpFish[number].c;
				tmpFish[number].c = tmpFish[changeFishNumber].c;
				tmpFish[changeFishNumber].c = tmpC;

				int tmp = tmpMAP[nr][nc];
				tmpMAP[nr][nc] = tmpMAP[f.r][f.c];
				tmpMAP[f.r][f.c] = tmp;

				break;
			}
		}
	}

	for (int move = 1; move <= 3; move++)
	{
		int nr, nc;

		nr = shark.r + dr[shark.dir] * move;
		nc = shark.c + dc[shark.dir] * move;

		if (map[nr][nc] == -1)
		{
			if (MAXANS < score) MAXANS = score;
			break; /* 더 이상 움직일 수 없는 경우 종료 */
		}

		DFS(nr, nc, shark.dir, score, tmpMAP, tmpFish);
	}
}

int main(void)
{
	input();

	DFS(1, 1, 0, 0, MAP, Fish);

	printf("%d\n", MAXANS);

	return 0;
}

A형은 tc가 여러 개이므로, 물고기의 dead 표시와 MAXANS를 초기화 하는 코드를 추가해야 한다.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 19238 : 스타트 택시 (삼성 SW TEST A형) (0)	2021.04.08
BOJ 19237 : 어른 상어 (삼성 SW TEST A형) (0)	2021.04.06
BOJ 20061 : 모노미노도미노 2 (삼성 SW TEST A형) (0)	2021.03.31
BOJ 17825 : 주사위 윷놀이 (삼성 SW TEST A형) (0)	2021.03.28
BOJ 17822 : 원판 돌리기 (삼성 SW TEST A형) (0)	2021.03.26

피로물든딸기의 라이브러리

BOJ 19236 : 청소년 상어 (삼성 SW TEST A형)

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

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 19236 : 청소년 상어 (삼성 SW TEST A형)

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

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바