[백준 1012번/JAVA] 유기농배추 (문제 풀이, 코드)

유기농배추

https://www.acmicpc.net/problem/1012

 

[문제]

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

 

[풀이]

DFS나 BFS중 하나를 써서 연결되어있는 놈들 visited 처리해주면 된다. 그리고 더 갈데가 없으면 그만하고.이 과정을 하나의 트랜잭션으로 보면 트랜잭션 하나당 배추벌레+1 이런 식.

 

[내 코드 알고리즘]

나는 좌표 생성시에 1인 좌표를 그냥 큐(togo)에다가 다 담았다.

그리고 togo 큐에 있는 좌표 하나씩 빼서 너비우선탐색을 해서, 갈 수 있는 곳은 -1을 줬다.

togo 큐에 있는 좌표를 뺄 때, 좌표의 값이 -1이면 그냥 탐색 안하도록 하면 끗!

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class pos {
	int x;
	int y;

	pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int M, N;
	static int[][] map;
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {
			// 숫자 받아오기
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			M = Integer.parseInt(st.nextToken()); // 가로길이
			N = Integer.parseInt(st.nextToken()); // 세로길이
			int K = Integer.parseInt(st.nextToken()); // 배추 위치 개수
			int sect = 0; //벌레 개수
			map = new int[M][N]; // 배추 지도
			Queue<pos> togo = new LinkedList<>(); // 모든 좌표 담기
			
			// 위치 좌표 받기!
			for(int j=0; j<K; j++) {
				st  = new StringTokenizer(br.readLine(), " ");
				pos p = new pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				map[p.x][p.y] = 1;
				togo.add(p);
			}
			// 본격적으로 찾기!
			while(!togo.isEmpty()) {
				pos p = togo.poll();
				if(map[p.x][p.y]== -1) continue;
				sect++;
				Search(p);
			}
			
			System.out.println(sect);
		}
	}
	public static void Search(pos start) {
		Queue<pos> next = new LinkedList<>(); // bfs 용 큐
		next.add(start);
		
		while(!next.isEmpty()) {
			pos p = next.poll();
			/* 상 */
			if(p.x>0)
				if(map[p.x-1][p.y] == 1) {
					map[p.x-1][p.y]=-1;
					next.add(new pos(p.x-1,p.y));
				}
			/* 하 */
			if(p.x<M-1)
				if(map[p.x+1][p.y]==1) {
					map[p.x+1][p.y]=-1;
					next.add(new pos(p.x+1,p.y));
				}
			/* 좌 */
			if(p.y>0)
				if(map[p.x][p.y-1]==1) {
					map[p.x][p.y-1]=-1;
					next.add(new pos(p.x, p.y-1));
				}
			/* 우 */
			if(p.y<N-1)
				if(map[p.x][p.y+1]==1) {
					map[p.x][p.y+1]=-1;
					next.add(new pos(p.x, p.y+1));
				}
		}
	}
}

[발전가능성]

상하좌우 부분은 배열 하나~두개로 충분히 더 짧게 만들 수 있으니 해보세용~!

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.