[BAEKJOON] - 1743번 : 음식물 피하기

1743번 문제 링크

⌛ 시간 복잡도

• 2초 : 200,000,000 회
• DFS 최대 횟수 : 가로 세로 (노드 + 에지)
  100 * 100 * ((2 * 4)+(98 * 98)+(3 * 98 * 4)) = 대략 100,000,000회
• DFS 사용 가능

📜 로직

해당 문제는 방문 여부를 확인하며, 상하 좌우의 인접 노드에 실제 쓰레기 값이 존재하는 지 확인하도록 dfs를 수행하면 됩니다.
1. map을 통해 음식물 쓰레기 좌표를 true로 초기화 해줍니다.
2. map에 등록된 좌표 중 방문하지 않은 좌표는 dfs 수행하며, dfs 수행 후 masx 값은 기존의 max값과 count를 비교 후 더 큰 값으로, count 값은 0으로 초기화 해줍니다.
3. dfs 수행 시, 방문 기록을 남기고 count를 추가해줍니다.
4.해당 노드 좌표의 상하 좌우에 위치한 인접 노드인 (x,y) → (x+1, y), (x-1, y), (x,y+1), (x,y-1) 를 확인하여 음식물 쓰레기 여부 확인 후 깊이 탐색을 수행하도록 구현합니다.

😀 성공

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

public class Main{
    static int N, M, count, max;
    static boolean[][] map, visited;
    static int[] dx = {-1,1,0,0}, 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()); //가로 길이
        int K = Integer.parseInt(st.nextToken()); //음식물 갯수
        
        map = new boolean[N][M]; // 쓰레기 좌표
        visited = new boolean[N][M]; // 방문 여부
        
        for(int i=0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) -1;
            int c = Integer.parseInt(st.nextToken()) -1;
            map[r][c] = true;
        }
        br.close();
        
        count = 0; max = 0;
        for(int i=0; i < N; i++){
            for(int j=0; j < M; j++){
                if(!visited[i][j] && map[i][j]){
                    dfs(i,j);
                    max = Math.max(count, max);
                    count = 0;
                }
            }
        }
        
        System.out.println(max);
    }
    
    static void dfs(int r, int c){
        visited[r][c] = true;
        count++;
        
        for(int i=0; i < 4; i++){
            int nowX = r + dx[i];
            int nowY = c + dy[i];
            
            if(nowX >= 0 && nowY >= 0 && nowX < N && nowY < M){
                if(!visited[nowX][nowY] && map[nowX][nowY]){
                    dfs(nowX,nowY);
                }
            }
        }
    }
}