반응형
목차
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
문제풀이
인접한 좌표가 연결되어 있는지 체크하는 문제이다.
인접하다해서 bfs, dfs가 떠올랐고,
상하좌우로 이동할 수 있다해서 dx, dy에 대한 내용이 떠올랐다
일반적인 bfs, dfs는 아래 사진처럼 1번에서 시작하면 연결된 9번까지 도착할 수 있었다.
문제에 bfs, dfs를 그대로 적용하면 어떻게될까?
(0,0)에서 시작한다 했을 때 (1,1)까지만 연결되어있기때문에 나머지는 탐색하지 못하고 끝나버린다!
그래서 bfs, dfs를 반복문안에 넣어서, 시작좌표를 다시 셋팅해주어야한다.
지렁이의 수도 이 반복문 안에 넣어서 체크해주자.
int count=0; //테스트 케이스마다 지렁이의 개수를 세야한다
//bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악할 수 있게한다
//가로 세로 좌표들을 하나씩 입력해주고
for (int j = 0; j < weight; j++) {
for (int k = 0; k < height; k++) {
//좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인한다
if(ground[j][k] == 1 && !check[j][k]){
//배추가 있고 체크안된 좌표에서부터 bfs로 연결된 곳을 파악한다
bfs(j, k); or dfs(j,k);
//지렁이의 개수는 인접한 곳마다 1개씩이다.
//인접한 곳을 모두 파악했으면 지렁이를 한마리 놓는다.
count++;
}
}
}
그림으로 보는 풀이(bfs, dfs)
- j= 0, k= 0일때
=> bfs(0,0)
=> bfs메서드 안에서 인접 좌표 탐색 (아래 그림 참고)
=> dfs(0,0)
=> dfs메서드 안에서 인접 좌표 탐색 (아래 그림 참고)
- j= 0, k= 1일때 => ground[0][1] = 0 이므로 패스
- j= 0, k= 2일때 => ground[0][1] = 0 이므로 패스
....
- j= 1, k= 0일때 => check[1][0] = true 이므로 패스
- j= 1, k= 1일때 => check[1][1] = true 이므로 패스
- j= 1, k= 2일때 => ground[1][2] = 0 이므로 패스
....
- j= 2, k= 3일때 => ground[2][3] = 0 이므로 패스
- j= 2, k= 4일때
=> bfs(2,4)
=> bfs메서드 안에서 인접 좌표 탐색 (아래 그림 참고)
=> dfs(2,4)
=> dfs메서드 안에서 인접 좌표 탐색 (아래 그림 참고)
... 계속 반복
제출코드
BFS 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] ground; //2차원 배열로 배추밭을 표현한다
static boolean[][] check; //2차원 배열로 배추가 있는 곳을 체크한다
static int weight; //배추밭의 가로
static int height; //배추밭의 세로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
weight = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());
ground = new int[weight][height];
check = new boolean[weight][height];
int K = Integer.parseInt(st.nextToken());
for (int j = 0; j < K; j++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
ground[x][y] = 1; //배추 좌표 입력
}
//===========================================================
//여기까지는 입력된 내용 저장하는 내용이다.
int count=0; //테스트 케이스마다 지렁이의 개수를 세야한다
//bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악할 수 있게한다
//가로 세로 좌표들을 하나씩 입력해주고
for (int j = 0; j < weight; j++) {
for (int k = 0; k < height; k++) {
//좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인한다
if(ground[j][k] == 1 && !check[j][k]){
//배추가 있고 체크안된 좌표에서부터 bfs로 연결된 곳을 파악한다
bfs(j, k);
//지렁이의 개수는 인접한 곳마다 1개씩이다.
//인접한 곳을 모두 파악했으면 지렁이를 한마리 놓는다.
count++;
}
}
}
System.out.println(count);
}
}
private static void bfs(int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
//bfs에서 queue의 역할은 다음 탐색할 좌표를 미리 저장해 놓는 것이다.
//bfs 1번 실행될때마다 인접한 곳을 모두 탐색하고 종료되니 bfs안에 queue를 선언했다.
queue.offer(new int[] {startX, startY});
//x, y좌표 저장
check[startX][startY] = true;
//시작좌표엔 배추가 있으니 미리 true로 처리해준다.
int[] X = {0, 0, -1, +1};
int[] Y = {-1, +1, 0, 0};
//배추가 상하좌우에 인접하면 이동할 수 있다.
//현재좌표에서 상하좌우 움직이는 좌표를 지정한다.
//queue가 비어있으면 더이상 인접한 배추가 없다는 뜻이다.
while(!queue.isEmpty()){
int[] poll = queue.poll();
//저장된 queue를 꺼낸다
//상하좌우 4가지 방법이니 for문 4번 반복
for (int i = 0; i < 4; i++) {
int x = poll[0] + X[i];
int y = poll[1] + Y[i];
//상하좌우 좌표 조정
//좌표가 배추밭을 벗어나게되면 다음 좌표를 체크해야한다
if(x < 0 || x >= weight || y < 0 || y >= height){
continue;
}
//상하좌우 움직인 좌표에 배추가 있고, 체크하지 않은 좌표이면
if(ground[x][y] == 1 & !check[x][y]){
queue.offer(new int[] {x, y});
//좌표를 저장한다.
check[x][y] = true;
//체크한다
}
}
}
}
}
DFS사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] ground; //2차원 배열로 배추밭을 표현한다
static boolean[][] check; //2차원 배열로 배추가 있는 곳을 체크한다
static int weight; //배추밭의 가로
static int height; //배추밭의 세로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
weight = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());
ground = new int[weight][height];
check = new boolean[weight][height];
int K = Integer.parseInt(st.nextToken());
for (int j = 0; j < K; j++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
ground[x][y] = 1; //배추 좌표 입력
}
//===========================================================
//여기까지는 입력된 내용 저장하는 내용이다.
int count=0; //테스트 케이스마다 지렁이의 개수를 세야한다
//bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악할 수 있게한다
//가로 세로 좌표들을 하나씩 입력해주고
for (int j = 0; j < weight; j++) {
for (int k = 0; k < height; k++) {
//좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인한다
if(ground[j][k] == 1 && !check[j][k]){
//배추가 있고 체크안된 좌표에서부터 dfs로 연결된 곳을 파악한다
dfs(j, k);
//지렁이의 개수는 인접한 곳마다 1개씩이다.
//인접한 곳을 모두 파악했으면 지렁이를 한마리 놓는다.
count++;
}
}
}
System.out.println(count);
}
}
private static void dfs(int startX, int startY) {
check[startX][startY] = true;
//시작좌표엔 배추가 있으니 미리 true로 처리해준다.
int[] X = {0, 0, -1, +1};
int[] Y = {-1, +1, 0, 0};
//배추가 상하좌우에 인접하면 이동할 수 있다.
//현재좌표에서 상하좌우 움직이는 좌표를 지정한다.
//상하좌우 4가지 방법이니 for문 4번 반복
for (int i = 0; i < 4; i++) {
int x = startX + X[i];
int y = startY + Y[i];
//상하좌우 좌표 조정
//좌표가 배추밭을 벗어나게되면 다음 좌표를 체크해야한다
if(x < 0 || x >= weight || y < 0 || y >= height){
continue;
}
//상하좌우 움직인 좌표에 배추가 있고, 체크하지 않은 좌표이면
if(ground[x][y] == 1 & !check[x][y]){
dfs(x, y); //해당 좌표로 dfs 실행
}
}
}
}
반응형
'Coding Test' 카테고리의 다른 글
| [백준] 1074번 Z 자바 (분할정복) (0) | 2022.02.24 |
|---|---|
| [백준] 2630번 색종이 만들기 자바 (분할정복) (0) | 2022.02.22 |
| [백준] 1697 숨바꼭질 1차원 BFS (0) | 2022.02.12 |
| [백준] 1966 프린터 큐 + 테스트케이스 (0) | 2022.02.11 |
| [백준] 9012 괄호 (0) | 2022.02.11 |
