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

---

문제 설명

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력
첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제 입력 1

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1

4

---

풀이

package silver1;

import java.util.*;
import java.io.*;

public class B1743_음식물피하기 {
	static int[] di = { 0, 1, 0, -1 };
	static int[] dj = { 1, 0, -1, 0 };
	static int Row;
	static int Col;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 통로 크기, 쓰레기 개수 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		Row = Integer.parseInt(st.nextToken());
		Col = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		map = new int[Row][Col]; //통로
		int[][] food = new int[K][2];
		
		// 음식물 입력
		for (int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			food[k][0] =r-1; food[k][1]=c-1; //음식물 좌표 넣기
			map[r-1][c-1] = 1; //음식물 생성
		}
		
		//제일 큰 음식물 구하기
		int max = 0;
		for (int[] f : food) { //각 음식물이 존재하는 곳으로 가서 그 구역의 음식물 크기 구함
			int i = f[0], j=f[1]; 
			int result = DFS(i, j, 1);
			max = result>max? result: max;
		}
		System.out.println(max);
	}
	
	static int DFS(int i, int j, int size) {
		map[i][j] = 0; //방문
		
		for (int n = 0; n < 4; n++) { //사방탐색 시작
			int ni = i + di[n];
			int nj = j + dj[n];
			
			if(ni>=0 && ni<Row && nj>=0 && nj<Col && map[ni][nj]==1) { //한방향으로 계속 이동 
				size = DFS(ni, nj, ++size); //다음 음식물로 이동하므로 size up
				// 결국 한방향의 끝에 도달했을 때  그 방향
			}
			//한방향으로 전진했는데 길 막히고 1도 없음! => 다음 for문으로 방향전환
		}
		// """""현재 위치에서 사방탐색이 전부 끝났음"""""
		return size;
	}
}

전체적인 흐름이 이전 문제 유기농 배추 어쩌구랑 유사하다.

대신 이번에는 음식물이 있는 곳의 사이즈를 구해야하는 점이 다르다.

코드 설명

size = DFS(ni, nj, ++size); //다음 음식물로 이동하므로 size up
				// 결국 한방향의 끝에 도달했을 때  그 방향

// """""현재 위치에서 사방탐색이 전부 끝났음"""""
		return size;

---

결과