DFS/BFS

• 좌표 (x, y) 를 2차원 배열에 담을 때는 보통 map[y][x] 로 접근한다.
• 최단거리/단계적 탐색은 BFS, 모든 경로/조합·백트래킹은 DFS가 자연스럽다.

---

좌표계 vs 배열 인덱스

일반 좌표 (x, y)

• 가로(x) 증가: → 오른쪽
• 세로(y) 증가: ↑ 위쪽

2차원 배열 인덱스 [row][col]

• 가로(col) 증가: → 오른쪽
• 세로(row) 증가: ↓ 아래쪽 (배열은 위→아래로 row가 증가)

변환 원칙

• 좌표 (x, y) → 배열 인덱스 (row, col) = (y, x)
• 즉, map[y][x] 로 저장/조회

언제 “반전”을 특히 신경써야 하나?

• 회전/대칭/색칠 문제, 패턴 매칭(오목·퍼즐·테트리스 등)
  → 좌표계와 배열 인덱스의 방향이 다르므로 변환 실수를 특히 조심
• 단순 방문표시/연결요소 탐색(예: 배추밭)은 보통 map[y][x]만 일관되게 쓰면 큰 문제 없음

자주 하는 실수

• (x, y)를 습관적으로 map[x][y]에 넣음
• 입력이 1-based 인데 0-based로 바로 사용 (필요 시 x-1, y-1)

---

DFS ↔ BFS 선택 기준 요약

• 전체 탐색/연결 요소 개수: DFS, BFS 모두 가능

  • DFS: 재귀(스택)로 구현 간결
  • BFS: 큐로 레벨 단위 균일 탐색

• 도달 가능 여부만 확인: 둘 다 가능 (그래프 형태에 따라 선택)

• 최단 거리(비가중 그래프): BFS (레벨 = 거리)

• 단계별 상태 확장/시뮬레이션: BFS (레벨이 1씩 증가)

• 모든 경로/조합 열거, 백트래킹: DFS (가지치기 용이, 메모리 절약)

• 메모리 관점:

  • 넓고 얕은 그래프 → BFS 큐가 매우 커질 수 있음
  • 깊고 가지 적은 그래프 → DFS가 효율적 (단, 재귀 깊이 주의)

빠른 선택표

목적/상황	추천
최단 거리(가중치 동일/없음)	BFS
레벨별 상태 확인(시뮬·퍼즐 단계 확장)	BFS
모든 경로/조합·백트래킹	DFS
단순 도달성	DFS/BFS 모두
메모리 제한(깊고 좁은 그래프)	DFS (반복/스택 권장)

---

미니 템플릿

BFS (격자 예시)

Queue<int[]> q = new ArrayDeque<>();
boolean[][] vis = new boolean[N][M];
q.offer(new int[]{sy, sx});
vis[sy][sx] = true;
int dist = 0;

while (!q.isEmpty()) {
    int sz = q.size();         // 레벨(거리) 한 층
    while (sz-- > 0) {
        int[] cur = q.poll();
        int y = cur[0], x = cur[1];
        // 목표 검사/처리 ...
        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d], nx = x + dx[d];
            if (ny<0 || nx<0 || ny>=N || nx>=M) continue;
            if (vis[ny][nx] || wall[ny][nx]) continue;
            vis[ny][nx] = true;
            q.offer(new int[]{ny, nx});
        }
    }
    dist++; // 레벨 증가 ⇒ 최단거리 +1
}

DFS (재귀, 백트래킹)

boolean[][] vis = new boolean[N][M];

void dfs(int y, int x) {
    vis[y][x] = true;
    // 처리 로직 ...
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d], nx = x + dx[d];
        if (ny<0 || nx<0 || ny>=N || nx>=M) continue;
        if (vis[ny][nx] || wall[ny][nx]) continue;
        dfs(ny, nx);
    }
    // 필요 시 백트래킹: vis[y][x] = false;
}

---

핵심 정리

• 입력 좌표가 (x, y) 인지, (row, col) 인지 확인
• 배열 접근은 map[y][x] 로 일관성 유지
• 1-based 입력은 0-based 변환 했는가? (x-1, y-1)
• BFS 최단거리면 레벨(큐 사이즈 기준) 로 관리했는가?
• DFS 재귀 깊이 한계(스택오버플로우) 고려? → 반복/명시적 스택 검토