[Silver I] 음식물 피하기 - 1743

문제 링크

성능 요약

메모리: 16236 KB, 시간: 160 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 2월 20일 11:01:23

문제 설명

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

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

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

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

입력

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

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

출력

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

코드

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

public class Main {
	static int n,m; //통로 크기
	static int[][] map; //통로 배열
	static boolean[][] visited; //통로 방문 여부
	static int result=1; //음식물 크기 측정할 변수
	static int[] dy= {0,0,-1,1}; //동서남북 이동
	static int[] dx= {-1,1,0,0}; //동서남북 이동
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		n= Integer.parseInt(st.nextToken());
		m= Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken()); //음식물 개수
		map= new int[n+1][m+1];
		visited=new boolean[n+1][m+1];
		int result_max=0; //최종적으로 가장 큰 음식물 크기
		for(int i=0; i<k; i++) {
			st=new StringTokenizer(br.readLine());
			int temp_n = Integer.parseInt(st.nextToken());
			int temp_m = Integer.parseInt(st.nextToken());
			map[temp_n][temp_m]=1; //음식물 있는 자리에 1로 표시
		}
		for(int i=1;i<=n; i++) {
			for(int j=1; j<=m; j++) {
				if(!visited[i][j]&&map[i][j]==1) { 
                //만약 방문하지 않았고 그 자리에 음식물이 있다면 ?
					result=1; //초기 음식물 크기 1
					dfs(i,j); //dfs 실행
					result_max=Math.max(result_max, result); 
                    //가장 큰 음식물인지 확인
				}
			}
		}
		System.out.println(result_max); //출력
	}
	public static void dfs(int x,int y) {
		visited[x][y]=true;
		for(int i=0; i<4; i++) {
			int temp_x=x+dx[i]; //동서남북 이동
			int temp_y=y+dy[i];
			if(temp_x<1 || temp_y<1||temp_x>n||temp_y>m) {
				continue;
			}
			if(map[temp_x][temp_y]==1 && !visited[temp_x][temp_y]) {
				result++; //음식물 더 있으면 크기 늘리기
				dfs(temp_x,temp_y); //dfs 알고리즘 실행
			}
		}
		return;
	}
}

해결 방법 설명

• "이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다." 라는 문제 설명에서 음식물 위치에서 동서남북 방향으로 더 음식물이 있는지 체크해야 한다.

static int[] dy= {0,0,-1,1}; //동서남북 이동
static int[] dx= {-1,1,0,0}; //동서남북 이동

• 각각 N,M,K를 입력받아 배열의 크기를 정하고 K개만큼의 음식물을 1로 표시해 설정해준다.
• 이중 for문을 통해 방문하지 않았고 음식물이 있는 자리인지 확인한다.
• 만약 맞다면 결과값을 1로 초기화하고 DFS를 실행해 그 위치에서 동서남북에 더 음식물이 있는지 확인하면서 결과값을 늘려나간다.
• DFS가 종료되면 그 결과값이 가장 큰 결과값인지 확인한다.
• 이중 for문 종료 후 결과값을 출력해준다.

---