알고리즘 스터디 6주차 3

문제번호

• 알고리즘 : 실버1
• 난이도 : 그래프 탐색

1743

1743

접근

• 100 X 100 크기의 통로를 가진다.
  • DFS도 가능한 문제
  • 최단 거리를 구해야되는가?
    • No, 가장 큰 음식물의 크기를 구하는 문제
    • DFS로 풀어야 겠다.

가정

• DFS로 문제를 푼다.
• DFS로 탐색을 하면서 재귀가 끝나면 다음 위치를 탐색하는데 이때 가장 큰 곳은 탐색을 많이 한 횟수가 된다.

풀어보기

import java.io.*;


public class Main {

    static int N;
    static int M;
    static int K;
    static int[][] road;
    static boolean[][] visited;
    static int max;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] read = bufferedReader.readLine().split(" ");
        N = Integer.parseInt(read[0]);
        M = Integer.parseInt(read[1]);
        K = Integer.parseInt(read[2]);

        road = new int[N ][M];
        visited = new boolean[N ][M ];

        for(int i = 0; i < K; i++){
            read = bufferedReader.readLine().split(" ");
            road[Integer.parseInt(read[0]) -1 ][Integer.parseInt(read[1]) - 1] = 1;
        }
        int maxValue = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                dfs(i, j);
                maxValue = Math.max(maxValue, max);
                max = 0;
            }
        }
        System.out.println(maxValue);
    }

    static void dfs(int x, int y){
        if(x < 0) return;
        if(y < 0) return;
        if(x >  N - 1) return;
        if(y > M - 1) return;
        if(visited[x][y]) return;
        if(road[x][y] != 1) return;
        visited[x][y] = true;

        max++;

        dfs(x, y+1);
        dfs(x, y-1);
        dfs(x+1, y);
        dfs(x-1, y);
    }
}

시행착오

• 문제를 보면 크기가 1부터 시작이라 헷갈렸다.
• 0부터 시작하는 수를 주는 것이 아니라 수를 받을 때 -1를 해서 받아야 했다.