[Java] 백준 1743번 [음식물 피하기] 자바

: ) YOUNG·2022년 3월 25일

알고리즘

목록 보기

69/422

백준 1743번
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는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

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

생각하기

최근에 DFS/BFS 문제만 풀어서 그런건지
그냥 그런건지 모르겠지만, 진짜 쉬운 문제였다.

DFS

DFS는 재귀함수를 통해 구현했다.

main문에서 전체를 탐색해서 map에 1이면서 방문하지 않는 조건에 걸리는
좌표값으로 DFS 재귀함수를 실행한다.

재귀함수를 실행 후 재귀되는 횟수만큼 count 값을 증가 해주면 결국 1이 붙어있는 갯수가 되니까

Math.max(max, count) 의 count 값이 정답이 된다.

BFS

BFS는 Queue를 이용해서 구현했다.
BFS도 마찬가지로 main문에서 전체를 탐색해서 map에 1이면서 방문하지 않는 조건에 걸리는 좌표값으로 BFS 재귀함수를 실행한다.

while( !que.isEmpty() ) 의 조건 반복을 통해서 인접한 1은 모두 count가 증가하게 되고

마지막에 나오는 count값이 인접한 1의 갯수가 된다.
Math.max(max, count) 의 count 값이 정답이 된다.

TMI

DFS/BFS 척척박사 되고싶다..

코드

DFS 사용

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

public class Main {
	static boolean visit[][];
	static int map[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};

	static int N, M;
	static int nowX, nowY;
	static int x, y;
	static int count = 1;


	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()) + 1;
		M = Integer.parseInt(st.nextToken()) + 1;
		int K = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visit = new boolean[N][M];
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
		}

		// 1을 만나면 탐색 시작
		int max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {

				count = 0;

				if(visit[i][j] == false && map[i][j] > 0) {
					DFS(j, i);
					max = Math.max(max, count);
				}
			}
		}

		System.out.println(max);
	}

	static void DFS(int x, int y) {
		visit[y][x] = true;
		count++;

		for(int i=0; i<4; i++) {
			nowX = x + dirX[i];
			nowY = y + dirY[i];

			if(Range_check() && visit[nowY][nowX] == false && map[nowY][nowX] > 0) {
				DFS(nowX, nowY);
			}
		}
	} // End of DFS

	static boolean Range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < M && nowY < N);
	} 
} // End of class

BFS 사용

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

public class Main {
	static boolean visit[][];
	static int map[][];
	static int dirX[] = {0, 0, -1, 1};
	static int dirY[] = {-1, 1, 0, 0};
	static Queue<Node> que = new LinkedList<>();

	static int N, M;
	static int nowX, nowY;
	static int x, y;
	static int count;

	static class Node {
		int x;
		int y;

		public Node(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()) + 1;
		M = Integer.parseInt(st.nextToken()) + 1;
		int K = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		visit = new boolean[N][M];
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
		}


		int max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				count = 1;
				if(visit[i][j] == false && map[i][j] > 0) {	

					BFS(j, i);
					max = Math.max(max, count);
				}

			}
		}

		System.out.println(max);
	}

	static void BFS(int x, int y) {
		que.offer(new Node(x, y));
		visit[y][x] = true;

		while( !que.isEmpty() ) {
			Node node = que.poll();

			for(int i=0; i<4; i++) {
				nowY = node.y + dirY[i];
				nowX = node.x + dirX[i];

				if(Range_check() && visit[nowY][nowX] == false && map[nowY][nowX] == 1) {     
					que.offer(new Node(nowX, nowY));
					visit[nowY][nowX] = true;
					count ++;
				}
			}

		}

	} // End of BFS

	static boolean Range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < M && nowY < N);
	}
} // End of class