그래프를 구현하는 방법 - 맵

종종 알고리즘 문제에서 그래프가 맵으로 주어지는 경우가 존재합니다.

이런 형태로요! 이렇게 주어진 맵은 그 맵을 기준으로 탐색을 이어가야만 합니다.

굳이 인접리스트나, 인접행렬로 바꾸려고 하면 머리만 아파요!

 

아, 그리고 위에서 주어진 표는 인접 행렬이 아니라 맵임을 명심하세요.

 

위의 맵에서 1은 갈 수 있는 지역, 0은 갈 수 없는 지역이라고 합시다. 

(육지 == 1 && 바다 == 0 혹은 길 == 1 && 벽 == 0 등등의 예시)

그럼 이걸 그래프로 표현하면 아래와 같은 모습이 됩니다. 

 

 

4방향 탐색과 방향 벡터

4방향 탐색은 위, 아래, 오른쪽, 왼쪽을 탐색하는 것을 의미합니다. 

그리고 보통 (y,x) 로 표현하곤 합니다. → 행, 열을 표현하기에 더욱 적합하기 때문

아래의 그림에서, dy, dx는 방향 벡터이며 direction_y, direction_x 를 의미합니다.

(위, 오른쪽, 아래, 왼쪽 순서대로 방향 벡터 구성)

 

 

코드로 구현해보면 다음과 같습니다. (상 → 우 → 하 → 좌 )

#include <bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int main(){
    int y = 0, x = 0; //시작점은 (0,0) 이라고 가정
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        cout << ny << " : " << nx << '\n';
    }
    return 0;
}

 

 

(심화) 8방향 탐색

사실 심화도 아닙니다. 그저 대각선으로 움직이는 방향 벡터를 추가해주면 됩니다.

dy, dx 배열의 길이가 각각 8이 되겠죠? 바로 코드로 구현해봅시다.

#include <bits/stdc++.h>
using namespace std;
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
    int y = 0, x = 0;
    for(int i = 0; i < 8; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        cout << ny << " : " << nx << '\n';
    }
    return 0;
}

 

 

---

방향 탐색 적용 문제

3 * 3 크기의 맵을 입력받고, 해당 맵은 1 혹은 0 으로 이루어져있다. (1은 갈 수 있는 지역, 0은 갈 수 없는 지역)

이때, 시작점인 (0,0)은 1일 때, 시작점부터 4방향을 기준으로 한칸씩 탐색해나가는 코드를 작성하라.

단, 방문한 정점은 다시 방문하지 않으며 첫 방문할 때마다 좌표를 출력해야 한다. 

#include<bits/stdc++.h>
using namespace std;
const int n = 3;
int a[n][n], visited[n][n];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
void go(int y, int x){
    visited[y][x] = 1;
    cout << y << " : " << x << "\n";
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        //잘못된 범위(존재하지 않는 위치) 참조하지 않도록 여기서 체크해야함
        if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
        if(a[ny][nx] == 0) continue; //갈 수 없는 지역
        if(visited[ny][nx]) continue; //이미 방문한 지역
        go(ny, nx);
    }
    return;
}

int main(){
	//n*n 크기의 맵을 입력 받음
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    go(0, 0);
}

 

오버플로우와 언더플로우 에러를 방지하기 위해 조건을 추가한 것만 유의해주세요!

항상 맵을 탐색할 때는, 맵의 범위를 벗어나지는 않는지 체크해야 합니다.

 

 

---

 

연결된 컴포넌트 (Connected Component)

이는 연결된 하위그래프를 말하며, 하나의 집합이라고 보면 됩니다. 

connected component에 포함되는 정점끼리는 연결되는 경로가 반드시 존재합니다. 

 

예시 그림을 보며, 간단히 이해하고 넘어갑시다.

 

왼쪽 그림에서,  연결된 컴포넌트의 수는 3개입니다. 

오른쪽 그림에서도, 연결된 컴포넌트의 수는 3개입니다.

 

참고로 연결되어있는지 여부에 따라 연결된 컴포넌트로 나누는데,

이렇게 컴포넌트 단위로 번호를 붙여가며 색칠하는 알고리즘이 존재합니다. 

그 알고리즘은 floodfill 이라고 부릅니다.