[백준] dfs - 1743번 음식물 피하기 (Java)

문제링크

1743번: 음식물 피하기

 

접근한 방법

• 연결된 노드의 묶음이 포인트인 문제이므로,
  dfs

 

---

풀이방법

1인 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다.

1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 1이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
   방문시마다 요소의 수를 더해준다.
3. 1~2번의 과정을 모든 노드에 반복

4. 묶여있는 범위마다의 요소의 값을 구한 후 그 최대값을 구한다.

---

소스코드 작성 방법

• 맵의 크기(n, m), 묶음 속 요소의 개수(result)를 전역 필드로 선언한다.
• 음식물이 위치한 정보(map), 방문 여부(visitied)를 전역 필드로 선언한다.
• 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
• dfs 메소드의 인자를 노드 번호(curR, curC)로 받는다.
  • vistied[curR][curC] = true로 하여 방문 처리
  • 방문할 때 마다 result++하여 음식물의 개수를 추가한다.
  • nextR, nextC를 for문 안에 선언하여 현재 위치에서 상 좌 하 우 위치를 탐색한다.
    • nextR은 curR + dx[dir]
      nextC는 curC + dx[dir] 로 상 좌 하 우 값을 선언해준다.
    • 상 좌 하 우 위치 이동 시 n * m 배열의 크기보다 크면 continue하여 넘어간다.
    • map[nextR][nextC] = 1이고 (음식물이있고) visited[nextR][nextC] = false로 아직 방문하지 않았다면
      dfs 메소드를 재귀적으로 호출하여 방문수행
• solution 메소드에서 1번 노드부터 마지막 번호 노드까지 탐색을 수행한다.
  * 방문하지 않은 노드만 방문 수행 !
  • temp를 선언하여 현재의 result값을 저장해두고
    dfs 메소드 호출이 끝나면 현재의 result값과 저장해둔 temp의 값을 비교하여
    최대값을 result에 저장한다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.StringTokenizer;

public class Q_1743_AvoidGarbage_20210521{
    public static int n, m;
    public static int[][] map;
    public static boolean[][] visited;
    public static int result;
    // 상좌하우
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static void solution(){
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    int temp = result;
                    result = 0;
                    dfs(i, j);
                    result = Math.max(result, temp);
                }
            }
        }

    }

    public static void dfs(int curR, int curC){
        visited[curR][curC] = true;
        result ++; // 방문할 때마다 개수 추가

        for (int dir = 0; dir < 4; dir++) {
            int nextR = curR + dx[dir];
            int nextC = curC + dy[dir];

            if(nextR < 1 || nextC < 1 || nextR >= n+1 || nextC >= m+1) continue;
            else if (map[nextR][nextC] == 1 && !visited[nextR][nextC])
                dfs(nextR, nextC);
        }

    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        map = new int[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];

        for (int i = 1; i < k+1; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            map[r][c] = 1;
        }

        solution();

        bw.write(result+"");

        br.close();
        bw.close();
    }
}