DFS/BFS 음료수 얼려먹기

dfs 또는 bfs로 풀 수 있는 문제다.

dfs 랑 bfs는 여러번 풀 다보니까 이진 탐색처럼 형태가 있다.

import java.util.*;

public class Main {
	public static int n, m;
    public static int[][] grapgh = new int[1000][1000];
    
    // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
    public static boolean dfs(int x, int y) {
    	// 주어진 범위를 벗어나는 경우에는 즉시 종료
        if (x <= -1 || x >= n || y <= -1 || y >= m) {
        	return false;
        }
        // 현재 노드를 아직 방문하지 않았다면
        if (graph[x][y] == 0) {
        	// 해당 노드 방문 처리
            grapg[x][y] = 1;
            // 상 하 좌 우의 위치들도 모두 재귀적으로 호출
            dfs(x -1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기(문자열로 입력을 받을 것이여서)
        
        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }
        
        // 모든 노드(위치)에 대하여 음료수 채우기
        int result = 0;
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < m; j++) {
            	// 현재 위치에서 DFS 수행
                if (dfs(i, j)) }
                	result += 1;
                }
            }
        }
        System.out.println(result); // 정답 출력 
    }
}

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

public class Main {

  public static int N, M;
  public static int[][] graph = new int[1000][1000];
  
  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());

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      String str = st.nextToken();
      
      for (int j = 0; j < M; j++) graph[i][j] = str.charAt(j) - '0';
    }

    int answer = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (dfs(i, j)) answer++;
      }
    }
    System.out.println(answer);
  }


  public static boolean dfs(int x, int y) {
    if (x <= -1 || y <= -1 || x >= N || y >= M) return false;

    if (graph[x][y] == 0) {
      graph[x][y] = 1;

      dfs(x - 1, y);
      dfs(x, y - 1);
      dfs(x + 1, y);
      dfs(x, y + 1);
      return true;
    }
    
    return false;
  }
}

참조

https://velog.io/@seongkyun/%EC%9D%8C%EB%A3%8C%EC%88%98-%EC%96%BC%EB%A0%A4-%EB%A8%B9%EA%B8%B0
.
https://velog.io/@dlgk0205/%EC%9D%8C%EB%A3%8C%EC%88%98-%EC%96%BC%EB%A0%A4%EB%A8%B9%EA%B8%B0-%EC%98%88%EC%A0%9C-5-10