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

: ) YOUNG·2022년 3월 25일
2

알고리즘

목록 보기
69/417
post-thumbnail

백준 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

0개의 댓글