-
[백준] 1012 유기농 배추 - Java알고리즘 문제 풀이 2024. 5. 30. 11:44
문제 - 유기농 배추
https://www.acmicpc.net/problem/1012
접근 방법
이 문제는 기본적인 그래프 탐색 dfs, bfs 문제이다
bfs 문제는 Queue를 활용해서 구현하면 되고 dfs는 재귀를 활용해서 풀면된다
작자는 dfs를 공부하고 있어서 dfs로 문제를 풀었다
코드 작성 (dfs)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int M; static int[][] map; static boolean[][] visited; static int[] dx = {0, -1, 0, 1}; static int[] dy = {1, 0, -1, 0}; static int count; public static void main(String[] args) throws IOException { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int testCount = Integer.parseInt(br.readLine()); for (int i = 0; i < testCount; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); map = new int[N][M]; visited = new boolean[N][M]; count = 0; for (int j = 0; j < K; j++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y] = 1; } for (int x = 0; x < N; x++) { for (int y = 0; y < M; y++) { if (map[x][y] == 1 && !visited[x][y]) { dfs(x, y); count++; } } } System.out.println(count); } } } public static void dfs(int x, int y) { visited[x][y] = true; for (int i = 0; i < 4; i++) { int ix = dx[i] + x; int iy = dy[i] + y; if (ix >= 0 && ix < N && iy >= 0 && iy < M) { if (!visited[ix][iy] && map[ix][iy] == 1) { dfs(ix, iy); } } } } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 2644 촌수계산 - Java (0) 2024.06.03 [백준] 4963 섬의 개수 - Java (1) 2024.06.02 [프로그래머스] 네트워크 - Java (0) 2024.05.30 [백준] 15670 N과 M(2) - Java (0) 2024.05.29 [백준] 2667 단지번호붙이기 - Java (0) 2024.05.27