음료수 얼려 먹기

• N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
• 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
• 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
• 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
• 00110
• 00011
• 11111
• 00000
• 아이스크림 총 3개 생성

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

 

처음에 푼 자바 코드(자바가 아직까지 익숙한 부분이 있어서) ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.System.*;

public class Main2 {

    static boolean[][] visited;
    static int[][] graph;

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

    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new boolean[n][m];
        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] = Integer.parseInt(str.charAt(j) + "");
            }
        }

        count = 0;

        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(!visited[i][j] && graph[i][j] == 0) {
                    visited[i][j] = true;
                    dfs(i, j);
                    count ++;
                }
            }
        }
        out.println(count);
    }

    private static void dfs(int n1, int n2) {
        for (int i = 0; i < 4; i ++) {
            int x = n1 + dx[i];
            int y = n2 + dy[i];
            if (x >= 0 && x < graph.length && y >= 0 && y < graph[n1].length && !visited[x][y]) {
                if (graph[x][y] != 0) {
                    continue;
                }
                visited[x][y] = true;
                dfs(x ,y);
            }
        }
    }
}

 

파이썬 코드

 

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))


# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or 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


# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j):
            result += 1

print(result)

 

파이썬 풀이 -> 자바 코드로 녹이기 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.System.in;
import static java.lang.System.out;

public class Main3 {

    static boolean[][] visited;
    static int[][] graph;
    static int n, m;

    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        visited = new boolean[n][m];
        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] = Integer.parseInt(str.charAt(j) + "");
            }
        }

        count = 0;

        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if (dfs(i, j)) {
                    count ++;
                }
            }
        }
        out.print(count);
    }

    private static boolean dfs(int x, int y) {
        if (x <= -1 || x >= n || y <= -1 || 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;
    }
}