[B0J]음식물 피하기(1743번)

티어 : Sliver 1
정답여부 : 정답
알고리즘 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
시간 제한 : 2초

💡문제

코레스코 콘도미니엄 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

💡문제 분석 요약

• 인근 음식물의 합이 가장 큰 값을 출력하면 되는 문제

💡알고리즘 설계

• M: 가로
• N : 세로
• arr : 각 학생들이 이용하는 곳
• foodWaste : 음식물

1. 각 숫자들읋 입력받고 음식물이 있는 위치에 1를 넣음
2. BFS , DFS 동작하면서 좌우상하에 음식물 즉 1이 있으면 cnt++
3. cnt중 가장 큰 cnt 값을 maxCnt에 넣어서 출력

💡시간복잡도

• O(N * M)

💡코드

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

public class Main {
    static int N, M, foodWaste;
    static int arr[][];
    static boolean visit[][];
    static int cnt;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        foodWaste = Integer.parseInt(st.nextToken());
        arr = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];
        
        for (int i = 0; i < foodWaste; i++) {
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            arr[a][b] = 1;
        }
        
        int maxCnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] == 1 && !visit[i][j]) {
                    cnt = 0;
                    bfs(i, j);
                    maxCnt = Math.max(maxCnt, cnt);
                }
            }
        }
        System.out.println(maxCnt);
    }

    private static void bfs(int x, int y) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] {x, y});
        visit[x][y] = true;
        cnt = 1;
        
        while (!que.isEmpty()) {
            int[] poll = que.poll();
            int poll_x = poll[0];
            int poll_y = poll[1];
            
            for (int i = 0; i < 4; i++) {
                int next_x = poll_x + dx[i];
                int next_y = poll_y + dy[i];
                
                if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= M && !visit[next_x][next_y] && arr[next_x][next_y] == 1) {
                    que.offer(new int[] {next_x, next_y});
                    visit[next_x][next_y] = true;
                    cnt++;
                }
            }
        }
    }
}

💡 틀린 이유

통과

BFS도 풀수 있고 DFS로도 풀수 있어 두가지 방식을 사용

💡 틀린 부분 수정 or 다른 풀이

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

public class Main {
    static int N, M, foodWaste;
    static int arr[][];
    static boolean visit[][];
    static int cnt;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        foodWaste = Integer.parseInt(st.nextToken());
        arr = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];
        
        for (int i = 0; i < foodWaste; i++) {
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            arr[a][b] = 1;
        }
        
        int maxCnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] == 1 && !visit[i][j]) {
                    cnt = 0;
                    //bfs(i, j);
                    dfs(i, j);
                    maxCnt = Math.max(maxCnt, cnt);
                }
            }
        }
        System.out.println(maxCnt);
    }

    private static void dfs(int x, int y) {
		visit[x][y] = true;
		cnt ++;
		 for (int i = 0; i < 4; i++) {
             int next_x = x + dx[i];
             int next_y = y + dy[i];
             if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= M && !visit[next_x][next_y] && arr[next_x][next_y] == 1) {
            	 dfs(next_x , next_y);
             }
		 }
		
	}
}

 

💡 느낀점 or 기억할정보

문제와 dfs,bfs에 값을 넣어줄때 차이만 있지 전체적인 코드는 비슷한거 같다.