valid(x, y) = (0 <= x < N) and (0 <= y < M) and (grid[x][y] ≠ wall)
알고리즘
BFS (최단 경로)
grid_bfs(grid, sx, sy, tx, ty): queue q dist[sx][sy] = 0 q.push((sx, sy)) while q not empty: (x, y) = q.pop() if x == tx and y == ty: return dist[x][y] for (dx, dy) in directions: nx = x + dx, ny = y + dy if valid(nx, ny) and not visited[nx][ny]: visited[nx][ny] = true dist[nx][ny] = dist[x][y] + 1 q.push((nx, ny)) return -1 # unreachable
DFS (연결 영역)
grid_dfs(x, y): if not valid(x, y) or visited[x][y]: return visited[x][y] = true area_size++ for (dx, dy) in directions: grid_dfs(x + dx, y + dy)
구현
// 격자 그래프 BFS, 최단 거리#include <bits/stdc++.h>using namespace std;int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};int grid_bfs(vector<string>& grid, int sx, int sy, int tx, int ty) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; q.push({sx, sy}); dist[sx][sy] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == tx && y == ty) return dist[x][y]; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } } return -1;}int main() { int n, m, sx, sy, tx, ty; cin >> n >> m >> sx >> sy >> tx >> ty; vector<string> grid(n); for (auto& s : grid) cin >> s; cout << grid_bfs(grid, sx, sy, tx, ty) << "\n";}
# 격자 그래프 BFS, collections.dequefrom collections import dequeimport sysinput = sys.stdin.readlinedef grid_bfs(grid, sx, sy, tx, ty): n, m = len(grid), len(grid[0]) dist = [[-1] * m for _ in range(n)] directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] q = deque([(sx, sy)]) dist[sx][sy] = 0 while q: x, y = q.popleft() if x == tx and y == ty: return dist[x][y] for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != '#' and dist[nx][ny] == -1: dist[nx][ny] = dist[x][y] + 1 q.append((nx, ny)) return -1n, m, sx, sy, tx, ty = map(int, input().split())grid = [input().strip() for _ in range(n)]print(grid_bfs(grid, sx, sy, tx, ty))
// 격자 그래프 BFS, Queue<int[]>import java.util.*;import java.io.*;public class Main { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static int gridBFS(String[] grid, int sx, int sy, int tx, int ty) { int n = grid.length, m = grid[0].length(); int[][] dist = new int[n][m]; for (int[] row : dist) Arrays.fill(row, -1); Queue<int[]> q = new LinkedList<>(); q.add(new int[]{sx, sy}); dist[sx][sy] = 0; while (!q.isEmpty()) { int[] cur = q.poll(); int x = cur[0], y = cur[1]; if (x == tx && y == ty) return dist[x][y]; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx].charAt(ny) != '#' && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.add(new int[]{nx, ny}); } } } return -1; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int sx = Integer.parseInt(st.nextToken()); int sy = Integer.parseInt(st.nextToken()); int tx = Integer.parseInt(st.nextToken()); int ty = Integer.parseInt(st.nextToken()); String[] grid = new String[n]; for (int i = 0; i < n; i++) grid[i] = br.readLine(); System.out.println(gridBFS(grid, sx, sy, tx, ty)); }}
stdin
5 5 0 0 4 4......###.......###......
결과
8
stdin
3 3 0 0 2 2....#....
결과
4
복잡도
항목
값
시간 (BFS)
O(N × M)
시간 (DFS)
O(N × M)
공간
O(N × M)
간선 수
최대 4NM (4방향) 또는 8NM (8방향)
각 칸 최대 1회 방문. 인접 칸 탐색 O(1).
변형 / 활용
1. 최단 경로 (BFS)
가중치 없는 격자 최단 경로. 미로 탈출.
int shortest_path = grid_bfs(grid, sx, sy, tx, ty);
2. 섬 개수 / 연결 영역 (DFS)
1 로 연결된 영역 개수.
int count_islands(vector<vector<int>>& grid) { int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1 && !visited[i][j]) { dfs(i, j); cnt++; } } } return cnt;}
3. 다익스트라 (가중치 격자)
각 칸에 비용. 우선순위 큐 사용.
priority_queue<tuple<int, int, int>> pq; // (cost, x, y)pq.push({0, sx, sy});dist[sx][sy] = 0;while (!pq.empty()) { auto [cost, x, y] = pq.top(); pq.pop(); if (cost > dist[x][y]) continue; for (auto [dx, dy] : dirs) { int nx = x + dx, ny = y + dy, ncost = cost + grid[nx][ny]; if (valid(nx, ny) && ncost < dist[nx][ny]) { dist[nx][ny] = ncost; pq.push({ncost, nx, ny}); } }}
4. 0-1 BFS (벽 부수기)
일반 이동 (비용 0), 벽 부수기 (비용 1). deque 사용.
deque<pair<int, int>> dq;dq.push_back({sx, sy});dist[sx][sy] = 0;while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); for (auto [dx, dy] : dirs) { int nx = x + dx, ny = y + dy; int w = (grid[nx][ny] == '#' ? 1 : 0); if (valid(nx, ny) && dist[x][y] + w < dist[nx][ny]) { dist[nx][ny] = dist[x][y] + w; if (w == 0) dq.push_front({nx, ny}); else dq.push_back({nx, ny}); } }}
💬 댓글