맵과 방향 벡터

N * M 크기의 배열로 표현되는 미로가 있습니다.

이럴 때 맵을 기준으로 탐색을 해야 합니다.

 

이걸 인접행렬로 생각하면 안됩니다.

맵은 맵입니다.

아 map이 아니고 행렬로 풀긴하는데

인접행렬 뭐 이런걸로 바꾸지 말라는 소리입니다.

 

보통 여기서 4가지방향을 탐색하라고 하는데

4가지 방향은 위, 아래, 오른쪽, 왼쪽이라고 칩시다.

그러면 Map에는 y와 x가 있을텐데요.

y, x를 중심으로 상하 좌우 4가지 방향 탐색을 해봅시다.

만약 1, 1이 중심이라고 치면

이런식으로 상 하 좌 우의 값들을 알겠죠?

그래서 보통 이것들을 dy, dx라고 합니다.

directionY, directionX해서

dy dx

그렇다면 여기서 시계방향으로 보았을 때

dy는

dy[-1, 0, 1, 0]이 될테구요.

dx는

dx[0, 1, 0 -1]이 될겁니다.

 

그렇다면 오른쪽으로 이동한다!라고 했을 때

nextX = x + dx[1]이 되겠네요.

 

다음 코드를 보면 이해가 더 쉬울겁니다.

 

#include <iostream>

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

보면 여기서 처음 i가 0일때

y는 -1만큼 이동하고 x는 0만큼 이동합니다.

그렇다면 위로 이동하겠네요.

그러면 i가 1일 때는요?

y가 0만큼 이동하고 x는 1만큼 이동합니다.

그러면 오른쪽으로 이동하면서 시계방향으로 순차적으로 탐색하죠?

 

만약 8방향이라면 어떨까요?

상, 상우, 우, 우하, 하, 하좌, 좌, 좌상 이렇게 말이죠.

이것도 뭐 쉽죠.

 

그림을 그리면 쉽습니다.

그러면

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

 

#include <iostream>

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으로 이루어진 맵이며 {0, 0}은 1을 보장받습니다.

{0, 0}부터 4방향을 기준으로 한칸씩 탐색하고 방문한 정점은 다시 방문하지 않습니다.

방문하는 좌표를 출력하는 코드를 작성해보죠.

참고로 0은 갈 수 없는지역이고 1은 갈 수 있는 지역입니다.

#include <iostream>

using namespace std;

const int n = 3;
int arr[n][n], visited[n][n];

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

void solve(int _y, int _x)
{
    visited[_y][_x] = 1;
    
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        // 음수거나 맵보다 크면 continue
        if (ny < 0 || ny >= n || nx < 0 || nx >= n)
            continue;
            
        // 0은 갈 수 없으니 continue
        if (arr[ny][nx] == 0)
            continue;
            
        // visited가 1이면 true 방문한거니 continue
        if (visited[ny][nx]))
            continue;
            
        solve(ny, nx);
    }
    
    return;
}

int main()
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
    
    // 0, 0 부터 시작
    solve(0, 0);
    return 0;
}

맞아요 이거 문제에요.

나도 다시 풀겁니다.

 

오 방금 풀고옴

여러분도 한 번 풀고 오세요.

 

끄읕