[이코테][Java] 음료수 얼려 먹기

문제 설명

N * M 크기의 얼음 틀에서 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주할 때, 얼음 틀에서 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

 

입력조건

• 첫 번째 줄에 N과 M
• 두 번째 줄부터 얼음 틀의 형태

출력조건

• 한 번에 만들 수 있는 아이스크림의 개수

입출력 예시

• 입력예시	출력예시
  4 5 00110 00011 11111 00000	3
  15 14 00000111100000 11111101111110 11011101101110 11011101100000 11011111111111 11011111111100 11000000011111 01111111111111 00000000011111 01111111111000 00011111111000 00000001111000 11111111110011 11100011111111 11100011111111	8

 

 

 

 

문제 풀이

• DFS 알고리즘 사용
• 특정 지점에서 상, 하, 좌, 우를 살펴보면서 아직 0(아직 방문하지 않은 지점)인 지점을 방문한다.
• 방문한 지점은 0 → 1 로 방문처리를 해준다.

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

public class Main {

    public static int graph[][];
    public static int n, m;
    public static int result;

    public static boolean dfs(int x, int y) {

        //주어진 얼음틀 범위를 벗어나면 종료
        if (x < 0 || y < 0 || x >= n || y >= m) {
            return false;
        }

        //현재 노드를 아직 방문하지 않은 경우
        if (graph[x][y] == 0) {
            graph[x][y] = 1;    //현재 노드를 방문 처리

            //상, 하, 좌, 우 방향으로 방문
            dfs(x - 1, y);
            dfs(x + 1, y);
            dfs(x, y - 1);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());   //세로 길이
        m = Integer.parseInt(st.nextToken());   //가로 길이

        graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(i, j) == true) {    //방문 처리가 됐다면 카운트
                    result++;
                }
            }
        }

        System.out.println(result);
    }
}

 

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈