코딩테스트-맵과 방향백터

맵(격자) 그래프 탐색과 방향벡터 (dy, dx)

격자(행렬) 형태로 주어지는 맵 문제는 코딩 테스트의 단골 유형이다. 이런 문제를 깔끔하게 푸는 핵심 도구가 방향벡터(dy, dx)다. 상하좌우 4방향 이동을 배열 하나로 처리해, 탐색 코드를 간결하게 만든다. (실제 네이버 코테에도 출제된 유형이다.)

---

1. yx 좌표계

맵 문제에서는 좌표를 (y, x) = (행, 열) 순서로 쓰는 것을 권장한다. 2차원 배열 접근이 a[행][열] = a[y][x]이기 때문에, 순서를 맞추면 헷갈릴 일이 줄어든다.

---

2. 방향벡터 정의

상하좌우 4방향의 좌표 변화량을 두 배열에 담아 둔다.

const int dy[] = {-1, 0, 1, 0};  // 상, 우, 하, 좌
const int dx[] = { 0, 1, 0, -1};

• (dy[0], dx[0]) = (-1, 0) → 위 (행 감소)
• (dy[1], dx[1]) = (0, 1) → 오른쪽 (열 증가)
• (dy[2], dx[2]) = (1, 0) → 아래 (행 증가)
• (dy[3], dx[3]) = (0, -1) → 왼쪽 (열 감소)

8방향 탐색이 필요하면 대각선까지 포함해 배열을 8칸으로 늘리면 된다.

// 8방향
const int dy[] = {-1,-1,-1, 0, 0, 1, 1, 1};
const int dx[] = {-1, 0, 1,-1, 1,-1, 0, 1};

---

3. 전체 코드

#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(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];

    go(0, 0);
}

/*
입력 예시
1 0 1
1 0 1
0 1 1
*/

---

4. continue 경계 검사가 핵심

이 유형에서 가장 중요한 건 세 가지 continue다. 특히 경계 검사는 배열 범위를 벗어난 접근(오버플로우/언더플로우)을 막는 필수 코드다. 순서도 중요하다 — 경계 검사를 반드시 먼저 해야 그 뒤 a[ny][nx] 접근이 안전하다.

• ① 경계 검사 : ny/nx가 0 미만이거나 n 이상이면 건너뛴다. → 배열 범위 밖 접근 방지
• ② 이동 가능 여부 : a[ny][nx] == 0(벽/막힌 칸)이면 건너뛴다.
• ③ 방문 여부 : 이미 방문한 칸이면 건너뛴다 → 무한 루프 방지

주의: 만약 경계 검사(①)를 뒤로 미루면, 범위를 벗어난 a[ny][nx]에 먼저 접근하다가 런타임 에러가 날 수 있다. 그래서 ①을 항상 맨 앞에 둔다.

---

정리

• 격자 맵은 (y, x) = (행, 열) 좌표계로 통일하면 실수가 준다.
• dy, dx 방향벡터로 4방향(또는 8방향) 이동을 for문 한 번에 처리한다.
• 탐색 시 경계 → 이동 가능 → 방문 순으로 continue 검사를 넣는다.
• 경계 검사는 반드시 배열 접근보다 먼저 수행한다.