맵과 방향백터

Q. 문제에서 맵(Map)으로 그래프를 표현한 경우 

- 맵(지도) 기반으로 문제를 풀어야 한다! 

(인접행렬 X, 인접리스트X)

 

1. 맵을 보고 "갈 수 있는 지점" 과 "갈 수 없는 지점"을 인식한다. 

- 갈 수 있는 지점  :  연결된 정점

- 갈 수 없는 지점 : 연결되지 않은 정점

1	1	1
1	1	1
1	0	0

 

2. 4가지 방향 탐색

(y, x 기반으로 하기)

시계방향으로 탐색 (상 → 우 → 하 → 좌)

 

3. 재귀적으로 한칸씩 이동

(인접리스트, 행렬과 마찬가지로)

---

Q. 3 * 3 맵을 입력받는다.

이 맵은 1과 0으로 이루어져있고 {0, 0}은 무조건 1이다.

{0, 0}부터 4방향을 기준으로 한칸씩 탐색해나가며 방문한 정점은 다시 방문하지 않으며 방문하는 좌표를 출력한다.

(0은 갈 수 없는 지역. 1은 갈 수 있는 지역)

 

#include <bits/stdc++.h>
using namespace std;

const int n=3;
int a[n][n], visited[n][n];     //3*3 맵, 방문 배열

//2. dx,dy 정의 
const int dy[]= {-1,0,1,0};
const int dx[] ={0,1,0,-1};

//5. go 재귀
void go(int y, int x){
	visited[y][x]=1;   //방문 
	cout << y <<" : " << x << "\n"; //출력 
	
	for(int i=0; i<n; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(ny < 0 || ny >= n || nx < 0 || nx >= n){
			continue;
		}
		//갈 수 없거나 방문했으면  continue 
		if(a[ny][nx] == 0) continue;
		if(visited[ny][nx]) continue;
		
		go(ny, nx);
	}
	
	return;
} 

int main(){
	//1. 현재 위치 
	int x=0; int y=0; 
	
	//3.맵 입력 받기 
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> a[i][j];
		}
	}
	
	//4. 0,0에서 방향 탐색 시작 
	go(y,x);
	
	return 0;
}

if(ny < 0 || ny >= n || nx < 0 || nx >= n){
	continue;
}

이 부분을 추가하여 overflow와 underflow를 방지해야한다.

(우리가 선언한 배열의 범위를 넘어가는지 확인)