코테에서 가장 자주 나오는 유형이 그래프 탐색이에요. 격자 최단거리, 연결 요소 세기, 도달 가능성 판별… 겉모습은 달라도 뼈대는 BFS/DFS 하나예요. 난이도별 6문제를 먼저 스스로 풀고, 힌트·정답 자바 코드로 확인해봐요.
그래프 탐색은 "연결된 것들을 빠짐없이 훑는" 알고리즘이에요. 정점과 간선으로 된 그래프뿐 아니라, 격자(2차원 배열)도 "칸=정점, 상하좌우 이웃=간선"인 그래프로 보면 똑같이 풀려요.
거의 모든 격자 문제가 이 뼈대에서 시작해요. dx/dy 한 쌍으로 상하좌우를 한 번에 훑어요.
int[] dx = {-1, 1, 0, 0}; // 상, 하
int[] dy = {0, 0, -1, 1}; // 좌, 우
// (x, y)에서 네 방향 이웃 살펴보기 (BFS 안쪽)
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // ① 범위 밖이면 건너뜀
if (visited[nx][ny] || map[nx][ny] == 0) continue; // ② 이미 갔거나 벽이면 건너뜀
visited[nx][ny] = true; // ③ 큐에 "넣을 때" 방문표시! (중복 방지)
queue.add(new int[]{nx, ny});
}visited=true가 그래프 탐색의 철칙이에요.① 문제. 정점 N개, 간선 M개짜리 방향 없는 그래프가 주어질 때, 연결 요소(서로 이어진 정점 덩어리)의 개수를 구하세요. 첫 줄에 N M, 다음 M줄에 간선의 두 끝 정점 u v가 주어져요.
② 입출력 예시.
6 5
1 2
2 5
5 1
3 4
4 62{1,2,5} 하나, {3,4,6} 하나 → 총 2개 덩어리.
u→v, v→u 양쪽에 넣어요.
import java.io.*;
import java.util.*;
public class Main {
static List<Integer>[] graph;
static boolean[] visited;
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());
graph = new ArrayList[n + 1]; // 1번~n번 정점
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph[u].add(v); // 방향 없는 그래프 → 양쪽에 추가
graph[v].add(u);
}
visited = new boolean[n + 1];
int count = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 새로운 덩어리의 출발점
count++;
dfs(i);
}
}
System.out.println(count);
}
static void dfs(int cur) {
visited[cur] = true;
for (int next : graph[cur]) {
if (!visited[next]) dfs(next);
}
}
}count++ 후 DFS로 그 덩어리 전체를 방문 처리해요. 한 번 방문한 덩어리는 다음 반복에서 visited에 걸려 건너뛰어지므로, 탐색을 새로 시작한 횟수 = 연결 요소 개수가 돼요. N이 최대 1000이라 재귀 깊이도 안전해요.
⑤ 복잡도. 각 정점·간선을 한 번씩만 봐요 → 시간 O(N + M), 공간 O(N + M)(인접 리스트).
⚖️ 백준 11724번에서 채점하기 (새 탭 ↗)① 문제. N×N 격자에 집(1)과 빈 땅(0)이 있어요. 상하좌우로 이어진 집들을 하나의 단지라 할 때, 단지 수와 각 단지의 집 수를 오름차순으로 출력하세요. (첫 줄 N, 다음 N줄은 공백 없이 0/1이 붙어 있음.)
② 입출력 예시.
7
0110100
0110101
1110101
0000111
0100000
0111110
01110003
7
8
9count만 얹으면 끝. 마지막에 크기 목록을 정렬해서 출력해요.
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[][] map;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine().trim());
map = new int[n][n];
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
map[i][j] = line.charAt(j) - '0'; // 붙어있는 숫자를 한 글자씩
}
}
visited = new boolean[n][n];
List<Integer> sizes = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
sizes.add(bfs(i, j)); // 새 단지 → 크기 기록
}
}
}
Collections.sort(sizes); // 오름차순
StringBuilder sb = new StringBuilder();
sb.append(sizes.size()).append('\n');
for (int s : sizes) sb.append(s).append('\n');
System.out.print(sb);
}
static int bfs(int si, int sj) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{si, sj});
visited[si][sj] = true;
int count = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
count++; // 꺼낼 때 집 1채 카운트
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (map[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true; // 넣을 때 방문표시
q.add(new int[]{nx, ny});
}
}
}
return count;
}
}bfs가 방문한 칸 수를 리턴하게 만든 게 포인트예요. 큐에서 꺼낼 때마다 count++하면 그 단지의 집 수가 나와요. 입력이 0110100처럼 공백 없이 붙어 있으니 line.charAt(j) - '0'로 한 글자씩 숫자로 바꿔요. 마지막에 Collections.sort로 오름차순 정렬 후 출력. DFS로 짜도 되지만, 격자가 커질 때 재귀 깊이가 부담되면 BFS가 안전해요.
⑤ 복잡도. 모든 칸을 한 번씩 방문 → 시간 O(N²), 공간 O(N²).
⚖️ 백준 2667번에서 채점하기 (새 탭 ↗)① 문제. N×M 미로에서 1은 이동 가능, 0은 벽이에요. (1,1)에서 (N,M)까지 상하좌우로 이동할 때 지나야 하는 최소 칸 수를 구하세요. (시작·도착 칸 모두 셈에 포함.)
② 입출력 예시.
4 6
101111
101010
101011
11101115visited 대신 거리 배열 dist를 쓰면 방문 여부(dist==0이면 미방문)와 거리를 동시에 관리할 수 있어 편해요. 이웃으로 퍼질 때 dist[다음] = dist[현재] + 1. 시작 칸을 1로 두면 도착 칸의 dist가 곧 답이에요.
import java.io.*;
import java.util.*;
public class Main {
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[][] map = new int[n][m];
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < m; j++) map[i][j] = line.charAt(j) - '0';
}
int[][] dist = new int[n][m]; // dist==0 이면 아직 미방문
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
dist[0][0] = 1; // 시작 칸도 1칸으로 셈
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (map[nx][ny] == 1 && dist[nx][ny] == 0) {
dist[nx][ny] = dist[x][y] + 1; // 한 칸 더
q.add(new int[]{nx, ny});
}
}
}
System.out.println(dist[n - 1][m - 1]);
}
}dist[nx][ny] == 0(아직 안 감)일 때만 값을 채우고 다시는 안 건드려요. 시작을 1로 뒀으니 도착 칸 값이 그대로 "지나온 칸 수"예요. 만약 시작을 0으로 두면 마지막에 +1을 해야 하니 주의!
⑤ 복잡도. 각 칸을 한 번씩 큐에 넣고 뺌 → 시간 O(N·M), 공간 O(N·M).
⚖️ 백준 2178번에서 채점하기 (새 탭 ↗)① 문제. M×N 상자에 익은 토마토(1), 안 익은 토마토(0), 빈 칸(-1)이 있어요. 하루가 지나면 익은 토마토의 상하좌우 토마토도 익어요. 모두 익는 데 걸리는 최소 일수를 구하세요. 이미 다 익었으면 0, 끝내 다 못 익으면 -1. (첫 줄 M N = 가로·세로.)
② 입출력 예시.
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 18익은 토마토가 여러 개면 전부 동시에 퍼져요. 위 예시는 한 개뿐이라 가장 먼 칸까지 8일 걸려요.
box[다음] = box[현재] + 1)하고, 끝나면 전체에서 가장 큰 값 − 1이 답이에요(시작을 1로 뒀으니). 다 돌린 뒤에도 0이 남아 있으면 -1.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken()); // 가로(열)
int n = Integer.parseInt(st.nextToken()); // 세로(행)
int[][] box = new int[n][m];
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
box[i][j] = Integer.parseInt(st.nextToken());
if (box[i][j] == 1) q.add(new int[]{i, j}); // 익은 것 전부 시작점!
}
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (box[nx][ny] == 0) { // 안 익은 칸만
box[nx][ny] = box[x][y] + 1; // 며칠째인지 누적
q.add(new int[]{nx, ny});
}
}
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (box[i][j] == 0) { // 끝까지 못 익은 칸 → 불가능
System.out.println(-1);
return;
}
max = Math.max(max, box[i][j]);
}
}
System.out.println(max - 1); // 시작을 1로 뒀으니 -1
}
}1로 뒀으므로 -1 보정해요. -1(빈 칸)은 조건 == 0에 안 걸려 자연히 무시돼요. 처음부터 0이 하나도 없으면 max가 1이라 답은 0이 돼요.
⑤ 복잡도. 각 칸을 한 번씩만 처리 → 시간 O(N·M), 공간 O(N·M).
⚖️ 백준 7576번에서 채점하기 (새 탭 ↗)① 문제. 수빈이는 점 N에, 동생은 점 K에 있어요(0 ≤ N, K ≤ 100,000). 수빈이는 1초에 X-1, X+1, 또는 X×2 로 이동할 수 있어요. 동생을 찾는 가장 빠른 시간(초)을 구하세요.
② 입출력 예시.
5 1745 → 10 → 9 → 18 → 17, 총 4초. (5→10 은 ×2, 10→9 는 −1, 9→18 은 ×2, 18→17 은 −1)
x-1, x+1, x*2 세 개. 1초당 비용이 모두 같으니 BFS로 최단 시간을 구해요. 위치 0~100000을 visited/dist 배열로 관리하고, 범위(0 ≤ nx ≤ 100000)를 꼭 체크하세요. x*2 때문에 위로 갔다가 -1로 다시 내려오는 경로가 최단일 수 있어요.
import java.io.*;
import java.util.*;
public class Main {
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 k = Integer.parseInt(st.nextToken());
final int MAX = 100001;
int[] dist = new int[MAX];
Arrays.fill(dist, -1); // -1 = 아직 방문 안 함
Queue<Integer> q = new LinkedList<>();
q.add(n);
dist[n] = 0; // 시작점, 0초
while (!q.isEmpty()) {
int x = q.poll();
if (x == k) break; // 동생을 찾으면 종료
int[] next = {x - 1, x + 1, x * 2};
for (int nx : next) {
if (nx < 0 || nx >= MAX) continue; // 범위 밖 차단
if (dist[nx] == -1) { // 처음 도달 = 최단
dist[nx] = dist[x] + 1;
q.add(nx);
}
}
}
System.out.println(dist[k]);
}
}dist가 곧 최소 초. x*2가 있어 위치가 N을 넘어갈 수 있으니 배열을 100001까지 잡고 범위 체크를 반드시 해요(안 하면 배열 밖 접근으로 터짐). N == K면 dist[k]가 처음부터 0이라 그대로 0이 출력돼요. DP로도 풀리지만, "최소 횟수"라는 시그널 그대로 BFS가 가장 자연스러워요.
⑤ 복잡도. 위치 수를 V=100,001이라 하면 각 위치를 한 번씩 방문 → 시간 O(V), 공간 O(V).
① 문제. 가로 M, 세로 N 밭에 배추가 K개 심겨 있어요(위치 X Y로 주어짐). 인접(상하좌우)한 배추 무리마다 지렁이 1마리면 충분할 때, 필요한 최소 지렁이 수(= 배추 덩어리 개수)를 구하세요. 첫 줄에 테스트케이스 수 T가 주어져요.
② 입출력 예시. (문제 지문의 예시 밭 — 5마리)
1
10 6 14
0 0
1 0
1 1
4 2
4 3
2 4
3 4
7 4
8 4
9 4
4 5
7 5
8 5
9 55(X, Y)로 심어요 → field[X][Y] = 1처럼 넣고, 격자 크기·이동 시 X는 0~M-1, Y는 0~N-1 범위를 헷갈리지 마세요. ② 테스트케이스마다 밭·방문 배열을 새로 만들어 초기화해야 이전 케이스가 안 섞여요.
import java.io.*;
import java.util.*;
public class Main {
static int m, n; // m=가로(X범위), n=세로(Y범위)
static int[][] field;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
field = new int[m][n]; // 테스트케이스마다 새로!
visited = new boolean[m][n];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
field[x][y] = 1; // (X, Y) 자리에 배추
}
int worms = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (field[i][j] == 1 && !visited[i][j]) {
worms++; // 새 덩어리 → 지렁이 1마리
bfs(i, j);
}
}
}
sb.append(worms).append('\n');
}
System.out.print(sb);
}
static void bfs(int si, int sj) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{si, sj});
visited[si][sj] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (field[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
}
}
}
}
}worms++ 후 BFS로 그 덩어리를 통째로 방문 처리 → 덩어리 수 = 지렁이 수. 실수 포인트 둘: (1) 입력이 좌표 X Y라 field[x][y] 인덱싱과 범위(x<m, y<n)를 일치시켜야 하고, (2) 매 테스트케이스마다 field·visited를 새로 할당해 이전 결과가 남지 않게 해야 해요. 여러 케이스라 출력은 StringBuilder에 모아 한 번에 찍으면 빨라요.
⑤ 복잡도. 테스트케이스 하나당 모든 칸 1회 방문 → 시간 O(M·N), 공간 O(M·N).
⚖️ 백준 1012번에서 채점하기 (새 탭 ↗)dx/dy 4방향 템플릿으로.dist 배열 하나로 방문 여부·거리를 같이 관리하면 깔끔해요.nx/ny가 0 ≤ nx < N 안에 드는지 이웃 접근 전에 검사(배열 밖 접근 방지).±1 보정.
💡 DFS 재귀는 격자가 아주 크면 StackOverflow가 날 수 있어요. 그럴 땐 BFS(큐)로 바꾸면 안전해요.