2022. 1. 5. 17:49ㆍPS (Program Solving)/BOJ (백준)
문제 설명
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
접근 방법 - 깊이 우선 탐색 (DFS)
백준의 1012번 문제는 DFS 및 BFS 문제이다. 필자는 DFS로 문제를 해결하였다.
필자는 아래의 흐름대로 규칙을 설정하고 코드를 작성해보았다.
필자는 배열을 이용할 시, 아래의 규칙을 정해두고 배열의 값을 바꾸었다.
0 : 배추가 없음
1 : 배추가 있음 & 지렁이가 방문하지 않음
2 : 배추가 있음 & 지렁이가 이미 방문함
코드의 실행 순서
1) 테스트 케이스 개수 입력받기 (+그 수만큼 전체 반복문 실행)
2) 가로 52, 세로 52인 배열 선언 및 전체적으로 0으로 초기화
(실제로 최대로 입력되는 것은 50*50이지만 DFS 알고리즘 수행할 시 상하좌우로 각각 1칸씩 여유가 되도록 하였다.)
3) 가로 및 세로, 배추의 개수, 각 배추의 위치를 순차적으로 입력받기 (+입력받은 배추의 위치의 값을 1로 바꾸기)
4) 최소로 사용하는 지렁이 개수 측정 위해 DFS 알고리즘 사용
지렁이가 방문하지 않았고 배추가 있는 한 좌표에 지렁이 하나를 놓은 뒤,
loof() 함수로 이 지렁이가 접근 가능한 공간을 확인한다.
loof() 함수 : 현 위치 및 상하좌우로, 지렁이 하나가 접근할 수 있는 공간들 모두, 방문했다는 의미로 2로 표시하는 함수
(재귀 함수로 구현하여 지렁이 하나가 방문할 수 있는 모든 영역을 검사한다.)
5) 최소로 사용한 지렁이의 개수를 출력한다. 그리고 종료한다.
성공한 코드
import java.util.Scanner;
//백준 1012번 코드
public class Main {
static int a[][]=new int [100][100];
public static void Loof(int k, int t) {
if(a[k][t]==1) {
a[k][t]++;
}
if(a[k][t+1]==1) {
a[k][t+1]++;
Loof(k,t+1);
}
if(a[k][t-1]==1) {
a[k][t-1]++;
Loof(k,t-1);
}
if(a[k+1][t]==1) {
a[k+1][t]++;
Loof(k+1,t);
}
if(a[k-1][t]==1) {
a[k-1][t]++;
Loof(k-1,t);
}
}
public static void main(String args[]) {
Scanner s=new Scanner(System.in);
int test1=s.nextInt();//테스트 케이스 개수
int count;//테스트 케이스 카운트 변수
for(count=0;count<test1;count++) {
//입력부분
for(int i=0;i<52;i++) {//i:열
for(int j=0;j<52;j++) {//j:행
a[i][j]=0;
}
}//배열 초기화
//입력부분
int w=s.nextInt();//가로길이 -> 행
int l=s.nextInt();//세로길이 -> 열
int n=s.nextInt();//배추 개수
for(int i=0;i<n;i++) {//배추 개수만큼 좌표입력 받기
int x=s.nextInt();//x좌표 -> 행
int y=s.nextInt();//y좌표 -> 열
a[y+1][x+1]=1;
}//배추 표시
//탐색부분
//0: 배추없음, 1:배추있음, 2:배추있음(방문완료)
int num=0;//지렁이 수 -> 출력 변수
for(int i=1;i<l+1;i++) {
for(int j=1;j<w+1;j++) {
if(a[i][j]==1) {
num++;
Loof(i,j);
}
}//for문 끝
}//2중 for문 끝
System.out.println(num);
}//테스트 케이스 for문 끝
System.exit(0);
}
}
제출 결과
(2020.01.20 백준 1012번 제출 결과)
(첫 DFS 문제여서 그런지 많이 헤맸던 게 보인다. 심지어 지금 보니 코드도 많이 엉망진창이다. 다음에 풀 땐 제대로 해야지.)
'PS (Program Solving) > BOJ (백준)' 카테고리의 다른 글
[백준 BOJ] 1085번 직사각형에서 탈출 (C++/cpp) (0) | 2022.01.05 |
---|---|
[백준 BOJ] 1075번 나누기 (C언어) (0) | 2022.01.05 |
[백준 BOJ] 1008번 A/B (C언어) (0) | 2022.01.04 |
[백준 BOJ] 1001번 A-B (C언어) (0) | 2022.01.04 |
[백준 BOJ] 1000번 A+B (C언어) (0) | 2022.01.01 |