문제 1012번(dfs, bfs)
: 배추흰지렁이는 상하좌우 네 방향에 위치한 다른 배추로 이동 가능
: 배추흰지렁이가 있는 배추들은 해충으로부터 보호받을 수 있다
: 예) 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요
0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
[입력]
: 첫째 줄에는 테스트 케이스 개수 T
: 둘째 줄에는 배추 밭 가로 M, 세로 N, 배추 심은 땅 개수 k
: 셋째 줄부터 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)
(두 배추의 위치가 같은 경우는 없다)
[출력]
: 필요한 최소의 배추흰지렁이 마리 수를 출력
[DFS 코드]
import java.util.*;
import java.io.*;
public class Main {
static int dirX[] = {0, 0, -1, 1};
static int dirY[] = {-1, 1, 0, 0};
static int arr[][];
static boolean visit[][];
static int now_x, now_y;
static int M, N, K;
static int count;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[M][N];
visit = new boolean[M][N];
for(int j=0; j<K; j++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = 1;
}
count = 0;
for(int j=0; j<M; j++) {
for(int k=0; k<N; k++) {
if(arr[j][k] == 1 && visit[j][k] == false) {
count++;
DFS(j, k);
}
}
}
sb.append(count).append('\n');
}
System.out.println(sb);
} // End Main
public static void DFS(int x, int y) {
visit[x][y] = true;
for(int i=0; i<4; i++) {
now_x = x + dirX[i];
now_y = y + dirY[i];
if(Range_check() && visit[now_x][now_y] == false && arr[now_x][now_y] == 1) {
DFS(now_x, now_y);
}
}
}
static boolean Range_check() {
return (now_x < M && now_x >= 0 && now_y < N && now_y >= 0);
}
}
[해설]
: static int dirX[] = {0, 0, -1, 1}; 상하좌우 좌표 설정
static int dirY[] = {-1, 1, 0, 0};
: static int arr[][]; 배추밭 2차원 배열 설정
static boolean visit[][]; 방문기록 설정
: static int now_x, now_y; 배추 심은 위치
static int M, N, K; 배추 밭 가로, 세로, 배추 심은 땅 개수
static int count = 0;
: int T = Integer.parseInt(br.readLine());
: for(int i=0; i<T; i++) { 테스트 케이스만큼 반복
st = new StringTokenizer(br.readLine()); 공백 단위로 끊어읽기
M = Integer.parseInt(st.nextToken()); 배추 밭 가로입력
N = Integer.parseInt(st.nextToken()); 배추 밭 세로입력
K = Integer.parseInt(st.nextToken()); 배추 심어진 땅 개수
arr = new int[M][N]; 가로 세로의 배추밭 배열
visit = new boolean[M][N];
for(int j=0; j<K; j++) {
st = new StringTokenizer(br.readLine()); 공백 단위로 끊어 읽기
int x = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 가로 입력
int y = Integer.parseInt(st.nextToken()); 배추 심은 위치 중 세로 입력
arr[x][y] = 1;
}
for(int j=0; j<M; j++) {
for(int k=0; k<N; k++) {
if(arr[j][k] == 1 && visit[j][k] == false) { 배추 땅이 1이면서 방문기록이 없다면 dfs 갱신
count++; 결과 카운트 해주기
DFS(j, k);
}
}
}
}
: public static void DFS(int x, int y) { dfs 실행
visit[x][y] = true; 기준 배열 지정
for(int i=0; i<4; i++) { 상하좌우 좌표 갱신
now_x = x + dirX[i];
now_y = y + dirY[i];
if(Range_check() && visit[now_x][now_y] == false && arr[now_x][now_y] == 1) {
DFS(now_x, now_y);
}
}
}
: static boolean Range_check() {
return (now_x < M && now_x >= 0 && now_y < N && now_y >= 0);
}
[BFS 코드]
import java.io.*;
import java.util.*;
import java.awt.*;
public class Main{
static int M,N,K,count;
static int dx[]={0,0,1,-1};
static int dy[]={1,-1,0,0};
static boolean visit[][];
static int arr[][];
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
while(T-->0){
st = new StringTokenizer(br.readLine());
M=Integer.parseInt(st.nextToken());
N=Integer.parseInt(st.nextToken());
K=Integer.parseInt(st.nextToken());
arr = new int[M][N];
visit = new boolean[M][N];
count = 0;
for(int i=0; i<K;i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y]=1;
}
for(int i=0; i<M; i++){
for(int j =0; j<N;j++){
if(arr[i][j]==1 &&!visit[i][j]){
bfs(i,j);
}
}
}
System.out.println(count);
}
}
static void bfs(int x, int y){
Queue<Point> q = new LinkedList<>();
q.add(new Point(x,y));
visit[x][y]=true;
while(!q.isEmpty()){
Point p = q.poll();
for(int i=0; i<4;i++){
int nx = p.x+dx[i];
int ny = p.y+dy[i];
if(0<=nx&&nx<M && 0<=ny&&ny<N && !visit[nx][ny] && arr[nx][ny]==1){
visit[nx][ny]=true;
q.add(new Point(nx,ny));
}
}
}
count++;
}
}
[해설]
: static int dirX[] = {0, 0, -1, 1}; 상하좌우 좌표 설정
static int dirY[] = {-1, 1, 0, 0};
: static int arr[][]; 배추밭 2차원 배열 설정
static boolean visit[][]; 방문기록
: static int count; 지렁이 개수
: int T = Integer.parseInt(br.readLine());
: while(T-->0) { 테스트 케이스만큼 반복
st = new StringTokenizer(br.readLine()); 공백 단위로 끊어읽기
M = Integer.parseInt(st.nextToken()); 배추 밭 가로입력
N = Integer.parseInt(st.nextToken()); 배추 밭 세로입력
K = Integer.parseInt(st.nextToken()); 배추 심어진 땅 개수
arr = new int[M][N]; 가로 세로의 배추밭 배열
visit = new boolean[M][N];
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()); 배추 심은 위치 중 세로 입력
arr[x][y] = 1;
}
for(int i=0; i<M; i++) {
for(int j=0; j<N; j++) {
if(arr[i][j] == 1 && !visit[i][j]) { 갈 수 있는 땅인지 매번 체크
bfs(i,j); 갈 수 있음 bfs 돌리기
}
}
}
System.out.println(count); 결과 출력
}
: static void bfs(int x, int y) { bfs 실행
Queue<Point> q = new LinkedList<>(); 큐선언
q.add(new Point(x,y)); Point 좌표 사용
visit[x][y]=true; 방문처리
while(!q.isEmpty()){
Point p = q.poll(); 큐에서 현좌표 꺼내기
for(int i=0; i<4;i++){
int nx = p.x+dx[i]; 현좌표 + 이동 = 새좌표 (x)
int ny = p.y+dy[i]; 현좌표 + 이동 = 새좌표 (y)
if(0<=nx&&nx<M && 0<=ny&&ny<N && !visit[nx][ny] && arr[nx][ny]==1){ 갈 수 있음 전진
visit[nx][ny]=true; 새좌표 방문처리
q.add(new Point(nx,ny)); 큐에 새좌표 추가
}
}
}
count++; 인접한 땅 bfs 검열이 모두 끝나면 지렁이 추가
}
이제 풀어보러 갈께요 :)
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *
'Baekjoon > [5] DFS & BFS' 카테고리의 다른 글
| [백준] 11724번 연결 요소의 개 JAVA (자바) 풀이 (0) | 2023.09.16 |
|---|---|
| [백준] 4963번 섬의 개수 JAVA (자바) 풀이 (0) | 2023.09.15 |
| [백준] 1260번 DFS & BFS JAVA (자바) 풀이 (0) | 2023.09.14 |
| [백준] 2644번 촌수계산 JAVA (자바) 풀이 (0) | 2023.09.12 |
| [백준] 2606번 바이러스 JAVA (자바) 풀이 (0) | 2023.09.11 |
