📃 문제
💡 문제풀이
마을에 있는 집에 전력을 공급하기 위해서
그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다.
즉, BFS 방식을 이용해서 문제를 해결하면 된다.
BFS (Breadth-First Search, 너비 우선 탐색)
BFS는 재귀적으로 동작하지 않고 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 선입선출(FIFO, First In First Out) 방식인 큐(Queue) 자료구조를 사용하여 '넓게' 탐색한다.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에 주로 두 노드 사이의 최단 경로를 찾거나, 가장 짧은 경로를 찾는 문제에 주로 사용한다.
💻 제출코드
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));
int N = Integer.parseInt(br.readLine());
int[][] town = new int[N][N]; // 마을의 상태를 저장하는 배열
boolean[][] visited = new boolean[N][N]; // 방문 여부를 저장하는 배열
for (int i = 0; i < N; i++) {
String[] row = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
town[i][j] = Integer.parseInt(row[j]);
}
}
// 발전기 개수
int count = 0;
// 모든 좌표를 순회하면서 BFS 수행 : 모든 집 찾기!
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (town[i][j] == 1 && !visited[i][j]) { // 집이 있고 방문하지 않았다면
bfs(i, j, N, town, visited);
count++; // BFS가 끝나면 발전기 개수 증가
}
}
}
System.out.println(count);
}
public static void bfs(int x, int y, int n, int[][] town, boolean[][] visited) {
// 상하좌우 이동
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y}); // 시작점 큐에 추가
while (!q.isEmpty()) {
int[] cur = q.poll(); // 현재 위치를 큐에서 가져옴
for (int k = 4; k-- > 0; ) { // 상하좌우 이동 검사
int nx = cur[0] + dx[k];
int ny = cur[1] + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 마을범위 밖이면 스킵
if (town[nx][ny] == 1 && !visited[nx][ny]) { // 집이 있고 방문하지 않았다면
q.offer(new int[]{nx, ny}); // 다음 위치를 큐에 추가
visited[nx][ny] = true; // 방문 처리
}
}
}
}
}
💭 후기
3주차는 탐색과 동적 프로그래밍 문제들이다. 확실히 1주차보다 문제들이 어렵다. 복습 열심히 해야지