[코드업/Codeup] C언어 : 1099 성실한 개미 문제 접근법 및 풀이 [기초-2차원배열]

# 1099 : [기초-2차원배열] 성실한 개미

미로 상자에 넣은 개미의 이동 경로를 출력하는 문제입니다. 먼저 주어진 문제를 보고 개미의 움직임을 파악해야 합니다.

문제에 따르면 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로만 움직인다고 합니다.

그리고 무조건 (2,2)에서 출발합니다. (배열은 0번 인덱스부터 시작하므로 배열의 위치로 따지면 (1,1)입니다. 1번째 행,

1번째 열의 위치입니다.)

• 먹이를 찾았다 : 배열에서 2를 발견하였다.
• 더 이상 움직일 수 없을 때까지 : 오른쪽, 아래쪽 모두 1(벽 또는 장애물)인 경우
• 오른쪽 또는 아래쪽 : 왼쪽, 위쪽을 신경쓰지 않아도 된다.

문제에서 주어진 정보를 파악했으니 입력과 출력을 확인합니다.

미로 상자의 구조와 먹이가 입력되면 개미가 이동한 경로를 9로 표시해 출력해야 합니다.

 

이제 알고리즘을 어떻게 짜야할지 생각해봅시다. 

우선 반복문과 2차원 배열을 이용해야합니다. 반복문을 돌릴 때는 개미가 움직이는 경로에 먹이가 있으면 무조건 멈추어야 합니다. 그렇다면 미로 배열을 maze라고 하고, 개미의 현재 위치를 (x,y)라고 했을 때 , maze[x][y] != 2인 동안 반복이 진행되어야겠네요!

while(maze[x][y] != 2)

 

이제 먹이를 찾았을 경우(개미의 경로에 2가 있을 경우) 반복문은 종료됩니다. 개미가 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로 이동하는 것도 구현해봅시다.

 

출력 예시를 확인했을 때 오른쪽과 아래쪽으로 모두 이동할 수 있는 경우 오른쪽으로 이동하는 것이 우선시되고 있습니다. 따라서 maze[x][y]가 개미의 현재 위치라고 했을 때의 경우의 수는 총 3가지입니다.

 

• maze[x][y+1]의 값이 0인 경우 (오른쪽으로 움직일 수 있는 경우)
• maze[x][y+1]의 값이 1인 경우(오른쪽으로 움직일 수 없는 경우)
• maze[x][y+1]의 값이 2인 경우 (오른쪽으로 움직일 수 있는 경우)

maze[x][y+1]의 값이 0과 2일 때의 결과가 똑같으니, 아래와 같이 정리할 수 있습니다.

 

• maze[x][y+1]의 값이 1이 아닌 경우 (오른쪽으로 움직일 수 있는 경우)
• maze[x][y+1]의 값이 1인 경우(오른쪽으로 움직일 수 없는 경우)

오른쪽으로 이동할 수 있다면 y를 1만큼 늘려주고 (오른쪽으로 1만큼 이동하는 것과 같은 효과), 그렇지 않다면 아래쪽을 확인하여 1인지, 1이 아닌지 확인합니다.

while (maze[x][y] != 2)
	{
		maze[x][y] = 9; // 개미의 현재 위치에 9를 저장
		
		if (maze[x][y + 1] != 1) y++; // 오른쪽이 1이 아닌 경우 다음 열로 이동
		else if (maze[x][y + 1] == 1)
		{
			if (maze[x + 1][y] == 1) break; // 아래쪽도 1인 경우 반복 종료
			else x++; // 그렇지 않다면 다음 행으로 이동
		}
		else break; // 혹시 모를 무한반복에 대비하여 안전하게 종료
	}
    
    maze[x][y] = 9; // 2를 만나서 반복이 종료되면 그 자리에 9가 남지 않으므로 추가

 

성실한 개미 문제는 이러한 알고리즘을 생각해낼 수 있었는지가 포인트였던 것 같습니다. 이제 배열을 입력받고 출력하는 코드를 추가해보겠습니다.

#include <stdio.h>

int main()
{
	int maze[10][10] = { 0 };
	int x = 1, y = 1;
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++) scanf("%d", &maze[i][j]);
	}

	while (maze[x][y] != 2)
	{
		maze[x][y] = 9;
		
		if (maze[x][y + 1] != 1) y++;
		else if (maze[x][y + 1] == 1)
		{
			if (maze[x + 1][y] == 1) break;
			else x++;
		}
		else break;
	}

	maze[x][y] = 9;

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++) printf("%d ", maze[i][j]);
		printf("\n");
	}

	return 0;

}

 

코드 지적은 언제든지 환영입니다!