[백준] S1 1743번 음식물 피하기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1743번: 음식물 피하기

[문제] 

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

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

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

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

[입력]

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

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

[출력]

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

 

---

[풀이]

BFS 방식

1. 값들을 입력받아준다.

2. 방문한 적 없고, 쓰레기라면 bfs 탐색을 한다.

3. bfs 탐색을 위한 큐를 만들어서 현재 좌표를 담아준다.

4. 현재 좌표를 방문처리해주고, 탐색을 한 칸이므로 쓰레기 크기를 1로 초기화해준다.

5. 사방 탐색을 해주고 범위를 벗어나거나, 이미 탐색한 곳, 쓰레기가 아닌 곳이라면 continue를 해주고 아니라면 추가 탐색을 위해 큐에 담아준다.

6. 탐색이 끝나면 최고 사이즈를 갱신해준다.

7. 결과를 출력한다.

 

DFS 방식

1. 값들을 입력받아준다.

2. 방문한 적 없고, 쓰레기라면 dfs 탐색을 한다.

3. 현재 좌표를 방문처리해주고 사이즈를 1 증가시켜준다.

4. 사방 탐색을 해주고 범위를 벗어나거나, 이미 탐색한 곳, 쓰레기가 아닌 곳이라면 continue를 해주고 아니라면 추가 탐색을 위해 dfs 탐색을 해준다.

5. 탐색이 끝나면 최고 사이즈를 갱신해준다.

6. 결과를 출력한다.

[접근]

1. dfs, bfs로 풀 수 있을 것 같았고 dfs는 최근에 많이 했으므로 bfs로 풀어보려고 하였다.

2. 하지만 기왕 하는 거 감이나 잡자는 마음으로 2가지 방법을 다 사용해서 풀어보았다.

[코드]

BFS 방식

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

public class Main {
	static int n, m, k;
	static int[][] map;
	static boolean[][] visited;
	static int size;
	
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};
	
	// 위치를 표시할 클래스
	static class point {
		int x;
		int y;
		
		public point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		map = new int[n][m];
		visited = new boolean[n][m];
		
		// 배열 채워주기
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			
			// 쓰레기의 위치
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			
			// 쓰레기 표시
			map[x][y] = 1;
		}
		
		// 쓰레기면서 방문한 적 없으면 bfs 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1 && !visited[i][j])
					bfs(i, j);
			}
		}
		
		System.out.println(size);
	}
	
	public static void bfs(int x, int y) {
		Queue<point> q = new LinkedList<>();
		q.add(new point(x, y));
		visited[x][y] = true; // 방문처리
		
		int cnt = 1; // 자기자신을 포함해야하니까 1로 초기화
		
		while (!q.isEmpty()) {
			point pos = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = pos.x + dr[i];
				int ny = pos.y + dc[i];
				
				if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] || map[nx][ny] != 1)
					continue;
				
				q.add(new point(nx, ny)); // 추가 탐색을 위한 큐 삽입
				visited[nx][ny] = true; // 방문 처리
				cnt++; // 쓰레기 크기 증가
			}
		}
		
		// 가장 큰 사이즈 찾기
		size = Math.max(size, cnt);
	}
}

 

DFS 방식

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

public class Main {
	static int n, m, k;
	static int[][] map;
	static boolean[][] visited;
	static int size, cnt;
	
	static int[] dr = {0, 0, -1, 1};
	static int[] dc = {-1, 1, 0, 0};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		map = new int[n][m];
		visited = new boolean[n][m];
		
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			
			// 쓰레기 좌표
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			
			// 쓰레기 표시
			map[x][y] = 1;
		}
		
		// 쓰레기고 방문한적 없으면 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					cnt = 0; // 개수 초기화
					dfs(i, j); // dfs 탐색
					size = Math.max(size, cnt); // 더 큰 사이즈 구하기
				}
			}
		}
		
		System.out.println(size);
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true; // 방문처리
		cnt++;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] || map[nx][ny] != 1)
				continue;
			
			dfs(nx, ny); // 추가 탐색
		}
		
	}
}