[C/C++] 맵(좌표) 동서남북 알고리즘 문제 고찰

오늘은 알고리즘 문제에 흔히 나오는 그래프(좌표) 탐색에 대해 알아보도록 하려고 한다. 흔히 알고리즘 문제에서 정사각형의 지도가 주어지고 그 안에서 보물을 찾는다든지, 탐색하면서 값을 변경하는 지 등등을 요구하는 문제들이 보인다.

이번에는 해당 위치에서 동서남북으로 탐색하는 예시를 들고자 한다.

맵(좌표) 탐색하기

크게 두 가지가 구현되어야 한다.

1) for문으로 현재 위치를 계속해서 바꿔 줌 (현재 좌표값이 계속해서 바뀌면서 탐색함)

2) 현재 위치 기준으로 동서남북으로 탐색하기

 

예시는 5x5 지도에서 인덱스 x=2, y=1에 있는 보석과 x=3, y=1에 있는 보석이 있고, 보석의 개수를 세는 문제이다.

00000

00000

01000

01000

00000

위와 같다.

첫 번째: 맵에 대한 값과 동서남북에 이용되는 배열 지정

- 5X5이므로 MAX 5로 설정을 하였고, int MAP[MAX][MAX]로 정수형 배열을 지정 해 주었다.

- 동서남북으로 사용될 배열을 지정 해 주었다. 아래와 같이 지정하고 for문으로 동서남북 탐색 예정이다.

모두 전역 변수로 선언하였다.

#include <iostream>
#include <string>
#define MAX 5

int MAP[MAX][MAX]={0,};
int cnt=0;
int dx[4]={0, 0, -1, 1};
int dy[4]={1, 0, -1, 0};

 

두 번째: 보석 숨겨 놓고 맵 출력 해 보기

이제 main 함수로 들어 와 보석 위치를 지정 해 보도록 할 예정이다. 또한 보석이 잘 들어갔는 지 한번 확인하는 알고리즘은 아래와 같다. 아래와 같이 입력하는 경우 각 행이 모두 출력된 후 행이 바뀌도록 구성된다. 따라서 모든 맵이 출력된다.

	MAP[2][1]=1;
	MAP[3][1]=1;
	for (int i=0; i<MAX; i++){
		for (int j=0; j<MAX; j++){
			printf("%d", MAP[i][j]);
		}
		printf("\n");
	}

00000

00000

01000

01000

00000

이와 같이 출력됨을 알 수 있다.

세 번째: 본격적으로 좌표 이동하면서 동서남북에 보석 탐색하기

1) for문을 통해 x, y 좌표가 모든 좌표를 탐색할 수 있도록 이중 for문을 구성한다.

2) nx, ny라는 신규 변수를 도입 해 준다. 이 신규 좌표로 현재 위치 기준 동서남북을 탐색할 것이다.

3) if문을 통해 nx, ny가 MAP의 인덱스를 넘어가면 그냥 넘겨버리도록 한다.

4) 1로 구성된 보석을 감지하면 보석을 줍고 0으로 바꿔준다. 그리고 보석 개수를 세는 cnt 변수를 증가시킨다.

	for (int x=0; x<MAX; x++){
		for (int y=0; y<MAX; y++){
			for (int k=0; k<4; k++)
			{
				int nx=x+dx[k];
				int ny=y+dy[k];
				if (nx<0||ny<0||nx>=MAX||ny>=MAX) continue;
				else{
					if (MAP[nx][ny]==1){
						cnt++;
						MAP[nx][ny]=0;
					}  
				}
			}
		}
	}
	std::cout<<cnt;

코드 전체

#include <iostream>
#include <string>
#define MAX 5

int MAP[MAX][MAX]={0,};
int cnt=0;
int dx[4]={0, 0, -1, 1};
int dy[4]={1, 0, -1, 0};

int main()
{
	MAP[2][1]=1;
	MAP[3][1]=1;
	for (int i=0; i<MAX; i++){
		for (int j=0; j<MAX; j++){
			printf("%d", MAP[i][j]);
		}
		printf("\n");
	}
	
	for (int x=0; x<MAX; x++){
		for (int y=0; y<MAX; y++){
			
			if (MAP[x][y]!=0) continue;
				
			for (int k=0; k<4; k++)
			{
				int nx=x+dx[k];
				int ny=y+dy[k];
				if (nx<0||ny<0||nx>=MAX||ny>=MAX) continue;
				else{
					if (MAP[nx][ny]==1){
						cnt++;
						MAP[nx][ny]=0;
					}  
				}
			}
		}
	}
	std::cout<<cnt;
	return 0;
}