[백준]1743번. 음식물 피하기(JAVA)

https://www.acmicpc.net/problem/1743

---

문제

---

풀이

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

public class Main {

    static boolean[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    static int r, c, garbage, count, max;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        garbage = Integer.parseInt(st.nextToken());

        map = new boolean[r+1][c+1];
        visited = new boolean[r+1][c+1];

        for (int i = 0; i < garbage; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            map[row][col] = true;
        }

        for (int i = 1; i < r+1; i++) {
            for (int j = 1; j < c+1; j++) {
                if(!visited[i][j] && map[i][j]) {
                    dfs(i, j);
                    max = Math.max(max, count);
                    count = 0;
                }
            }
        }

        System.out.println(max);
    }

    public static void dfs(int x, int y) {
        count++;
        visited[x][y] = true;

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

            if(nowX >= 1 && nowX <= r && nowY >= 1 && nowY <= c){
                if (!visited[nowX][nowY] && map[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }

    }

}

dfs를 이용한 문제풀이다.

static int dx[] = {-1, 1, 0, 0};
static int dy[] = {0, 0, -1, 1}; 네가지 방향 탐색에 대한 좌표 설정이다. 이는 도구정리에서 다시 한번 정리를 확실히 익혀야 할 것이다.

 

사용자 입력을 통해 좌표에 대한 정보를 설정한 뒤에(도구정리와 다르게 간선이 아니기 때문에 [x][y] = [y][x] =true 같은 설정은 하지 않는다.

 

시작 좌표에 대해 탐색을 진행하고 이 때 이어지는 dfs에 대해서는 count++를 통해 정보를 체크한다. 또한 이 값이 최대값인지는 모르기때문에 이 것을 max와 비교해서 저장한다. dfs의 재귀까지 최종적으로 마쳐지고 다른 좌표에 대한 탐색을 진행하기 시작할 때는 count=0으로 초기화 해준다.