Map, Direction

맵과 방향벡터

어렵게 생각할 필요없이 이 그림 하나로 쉽게 이해할 수 있다. 그림의 좌표는 (y,x)로 기준을 잡았다. 졸라맨 캐릭터가 있는 좌표의 위치를 (1,1)이라고 가정을 했을 때 각 위치를 표현을 했고, 주황색의 좌표는 변화율을 나타낸다. ex) 1,1 → 0,1은 y가 -1만큼 줄었음을 나타낸다.

문제

그러면 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];
int visited[n][n];
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
int 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;
        }
        if(a[ny][nx] == 0){
            continue;
        }
        if(visited[ny][nx]){
            continue;
        }
        go(ny,nx);
    }
}

int main(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    go(0,0);
    return 0;
}

방문한 정점이라는 배열은 visited 배열을 통해서 방문을 확인한다. 방문한 배열을 1로 체크를 해두고, 방문하지 않은 배열을 0으로 표기한다. 그러므로 for(int i = 0; i < n; i++) 반복문에서 dy[i]와 dx[i] 값을 이용하여 현재 좌표 (y, x)에서 새로운 좌표 (ny, nx)를 구하게 된다. 그리고 각 검증에서 좌표의 범위를 벗어나거나, 0인 좌표는 이동할 수 없거나 탐색하지 않을 필요가 있는 경우이다. 그리고 이미 방문했던 좌표는 방문할 필요가 없으므로 건너뛴다. 그리고 다음의 if의 검증들을 다 넘어가면 재귀호출을 통해 다음 반복을 이어간다.

Reference

나의 뇌