[java/python] 4963 - 섬의 개수

4963번: 섬의 개수 (acmicpc.net)

4963번: 섬의 개수

이제까지 배웠던 알고리즘을 복습하며

파이썬과 자바로 풀어보고 있다.

 

기존에 풀어봤던 dfs/bfs 랑은 좀 다르게 이 문제는 대각선으로도 이동을 한다.

그외엔 어려운 점이 없었다.

물론 파이썬은..

 

그러나 자바는 아직 예상치 못하게 마주하는 난관들이 있는데

 아직 코테 문법이 익숙하지 않은 탓인 것 같다.

그래서 정리해보려고 한다.

 

우선 파이썬 코드는 다음과 같다.

[Python]

# 4963 섬의 개수

import sys
from collections import deque
input = sys.stdin.readline

dx=[0,0,1,-1, 1, -1, 1, -1]
dy=[1,-1,0,0, -1, 1, 1, -1]

def bfs(i, j, h, w):
    q = deque()
    q.append((i, j))
    graph[i][j] = 0
    
    while q:
        next_h, next_w = q.popleft()
        
        for n in range(8):
            x2= next_h+dx[n]
            y2 =next_w+dy[n]

            if x2 <0 or x2 >= h or y2 <0 or y2 >=w:
                continue
            if graph[x2][y2] == 1:
                graph[x2][y2] = 0
                q.append((x2, y2))
   
    return 1

while True:
    w, h = map(int, input().split())
    
    if w == h == 0:
        break
    
    graph=[[] for _ in range(h)]
    
    for i in range(h):
        arr = list(map(int, input().split()))
        graph[i].extend(arr)
    
    cnt=0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                cnt+=bfs(i, j, h, w)
    print(cnt)

 

다음은 자바 코드이다.

[Java]

package graph_bfs_dfs;

import org.w3c.dom.Node;

import java.io.*;
import java.sql.Array;
import java.util.*;
public class Aug5Week_4963_Ssi {
    /***
     * 그래프 크기 변동이 없을 경우 배열 사용하는 것이 편리
     * 배열을 사용할 경우 dfs를 돌며 값을 바꾸기 보다 check 배열을 하나 더 만들자
     * 어레이리스트는 그래프 입력받을 때 불편함.
     *
     * 큐 사용시 add : 예외 발생 // offer : false 리턴
     */
    static int graph[][];
    static boolean visit[][];
    static int dx[] = {0,0,1,-1, 1, -1, 1, -1};
    static int dy[] = {1,-1,0,0, -1, 1, 1, -1};
    static class Node{
        int x , y;

        public Node(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    public static int bfs(int i, int j, int w, int h){
        Queue<Node> q = new LinkedList<Node>();
        visit[i][j] = true;
        q.offer(new Node(i,j));

        while(!q.isEmpty()){
            Node node = q.poll();

            for(int k=0;k<8;k++){
                int x2 =dx[k]+ node.x;
                int y2= dy[k]+node.y;

                if(x2<0 || x2>=h || y2 <0 || y2 >=w){ continue; }
                if(graph[x2][y2] == 1 && !visit[x2][y2]){
                    visit[x2][y2] = true;
                    q.offer(new Node(x2, y2));
                }
            }
        }
        return 1;
    }


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

        while (true){
            st = new StringTokenizer(bf.readLine());

            // w, h 입력
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            // 종료 조건
            if (w == 0 && h == 0){
                break;
            }

            // 그래프
            graph = new int[h][w];
            visit = new boolean[h][w];

            for(int i=0; i<h;i++){
                st = new StringTokenizer(bf.readLine());
                for(int j=0; j<w;j++){
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int cnt=0;
            for(int i=0; i<h;i++){
                for(int j=0;j<w;j++){
                    if(graph[i][j] == 1 && !visit[i][j]){
                        cnt += bfs(i, j, w, h);
                    }
                }
            }
            System.out.println(cnt);

        }
    }
}

 

지난번에 문제를 풀 때는 graph를 arrayList를 사용하였는데 (길이가 일정하지 않았다.)

이 문제에서는 입력받는 것도 그렇고 그냥 배열을 사용하는게 훨씬 간편한 듯하다.

 

파이썬으로 먼저 풀고 코드를 보며 자바로 다시 풀어보는 중인데

문법이 다르다 보니 완벽하게 똑같이 작성은 할 수가 없다.

 

어쨌든 그래서 자바에서는 섬을 지나갔는지를 체크하는 배열을 하나 더 만들어서 이중으로 체킹을 했다.