맵(지도)과 방향벡터(direction vector)

https://blog.naver.com/jhc9639/222289089015

[알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회

---

갈 수 있는 곳 1, 없는 곳 0으로 표현된다고 할 때 / y,x의 증감폭 나타내봐.

 

4방향(상하좌우)을 탐색!

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

// dy : direction y, ny : next y

for(i=0 ~4)
ny = y + dy[i];
nx = x + dx[i];

---

예제

Q. {0,0} 좌표에서 dy, dx를 만들어 4방향 (상하좌우)을 탐색하며 좌표를 출력하시오.

#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;

    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        cout << ny << " : " << nx <<'\n';
    }

    return 0;

}

 

Q. {0,0} 좌표에서 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 < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        cout << ny << " : " << nx <<'\n';
    }

    return 0;

}

 

Q. 3*3맵을 입력받아야 한다.

이 맵은 1,0으로 이루어져있고 {0,0}은 무조건 1임을 보장한다.

{0,0}부터 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];

        // 1. 오버플로우, 언더플로우 방지 - 가장 먼저 선행되어야 하는 조건!
        if(ny<0 || ny>=n || nx < 0 || nx >=n) continue; 
        // 이동할 수 있는 곳만 이동
        if(a[ny][nx]==0) continue;
        // 방문한 적 있다면 패스
        if(visited[ny][nx]) continue;
    }
}
 
int main(){
    for(int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    go(0,0);
}

 

이런 블록코딩의 기본적 로직과 비슷한듯..