[C++]BFS_상하좌우 이동 배열(dx,dy)

BFS알고리즘 문제를 풀때 늘 사용하는 배열이 있다. 

 

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

 

 

바로 이차원 배열의 탐색을 위해서 사용하는 dx와 dy배열이다. 

이 배열을 이용해 상하좌우를 탐색하는데 지금까지 방향을 잘못알고있었다.

만약 이 배열이 동,남,서,북 이라는 것을 알고있다면 이 글을 읽을 필요 없다. 

 

 

이런 당연한 배열을 포스팅할생각 없었지만 

어제 https://www.acmicpc.net/problem/15683

15683번: 감시

이 문제를 풀다가 내가 이 배열에 대해서 잘못알고있었음을 깨달았다. 

그래서 잊어버리지않기위해,  이 글을 본 사람들은 나와 같은 잘못된 이해를 하지않았으면 하는 바람에서 글을 쓴다.

 

 

 

 

 

#include<iostream>
#include<queue>
using namespace std;
#define x first
#define y second

int mp[501][501];
int vis[501][501];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
		}
	}
	queue<pair<int, int> > Q;
	int cnt = 0; // 그림의 개수
	int mx = 0; // 그림의 넓이
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] || mp[i][j] == 0) continue;
			cnt++;
			Q.push({ i,j });
			vis[i][j] = 1;
			int area = 0;
			while (!Q.empty()) {
				pair<int, int> cur = Q.front();
				Q.pop();
				area++;
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.x + dx[dir];
					int ny = cur.y + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (vis[nx][ny] || mp[nx][ny] == 0) continue;
					Q.push({ nx,ny });
					vis[nx][ny] = 1;
				}
			}
			mx = max(mx, area);
		}
	}
	cout << cnt << "\n" << mx;
}

 

[참고] -> 백준에 그림 문제의 코드이다. 보통 이런 코드로 bfs를 푼다. 

 

 

dx,dy 배열

 

이런식으로 묶여서 배열이 이용된다. 나는 주로 dir이라는 변수를 만들어 이용한다. 

 

지금까지 나는수학에서  x는 좌우, y는 상하를 의미한다고 배웠기때문에

 

수학에서의 좌표계

위 배열에서 x가 0, y가 1이니까 북쪽이고, x가 1, y가 0이니까 동쪽, x가 0이고, y가 -1이니까 남쪽 이런식으로

북, 동, 남, 서쪽 이라고 생각하고 있었다. 

 

 

 

 

 

물론 어떻게 코드를 작성하느냐에 따라 다르겠지만 내 코드에서는 이렇게 생각하는것은 틀렸다. 

보통 나는 세로를 x로 놓고, 가로를 y로 놓는다. [위의 코드 참조] 

 

 

이차원배열-x,y

즉 이차원에서 좌표를 위 그림처럼 생각하고

x,y 

x, y 를 이처럼 생각해주어야한다. 

그러므로

 

dx,dy 배열

  이 두 배열은 차례로 동, 남, 서, 북 을 탐색한다.