백준 4963번 - 섬의개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

문제를 읽고 위의 예시 그림의 섬의 개수를 세어본다면, 총 3개의 영역으로 나뉘어져 섬의 개수는 3개인것을 알 수 있다.

 

즉 기준이되는 섬의영역(* 표시) 가 있을때 상하좌우 대각선까지

 

모두 포함해서 하나의 섬으로 이어질 수 있다는 것이다.

 

 

(c,r) 순서쌍을 생각하자 c : 행 , r : 열

 

그럼 현재 (c,r) 을 기준으로 빨간색범위에 있으면 모두 하나의 섬으로 봐준다.

 

또한 이 문제는 영역을 구하는 문제이므로 DFS 알고리즘을 사용해준다.

 

2차원 방문배열을 따로 만들필요 없이 만약 방문을 하면

 

해당 배열값 자체를 0으로 바꿔주면

방문한걸로 표시되어 다시는 방문하지 않게될 것이다.

 

(해당 처리가 없으면 콜백지옥에 빠지게 된다. 조심하자!)

또한 "0 0" 이 입력되기 전까지 여러개의 이차배열을 받아 섬의 개수를 구할 것이므로

적절한 while 문의 사용도 필요하다. 

 

 

그럼 아래의 코드를 보면서 로직을 구현해보자.

 

1. JAVA

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

public class Main {

    static int N,M;
    static int[][] map;
    static int[] dr = {0,0,1,-1,1,-1,1,-1};
    static int[] dc = {1,-1,0,0,1,-1,-1,1};

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

        while (true) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(stk.nextToken());
            N = Integer.parseInt(stk.nextToken());
            
            int islandCnt = 0;

            if (M == 0 && N == 0) break;
            
            map = new int[N][M];

            for (int i = 0; i < N; i++) {
                stk = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(stk.nextToken());
            }

            for (int i = 0; i < N*M; i++) {
                int r = i/M;
                int c = i%M;

                if (map[r][c] != 0) {
                    dfs(r, c);
                    islandCnt++;
                }
            }
            
            bw.write(islandCnt + "\n");
        }
        
        bw.close();
        br.close();
    }    
    
    static void dfs(int r, int c){
        
        map[r][c] = 0;
        
        for (int i = 0; i < 8; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];

            if (newR >= 0 && newC >=0 && newR < N && newC < M && map[newR][newC] != 0) dfs(newR, newC);
        }
    }
}

 

 

2. C++

#include <iostream>
#include <cstring>

using namespace std;

int N,M;
int map[50][50];
int dr[8] = {0,0,1,-1,1,-1,1,-1}; //행에 관한 방향데이터
int dc[8] = {1,-1,0,0,1,-1,-1,1}; //열에 관한 방향데이터


void dfs(int r, int c)
{
   map[r][c] = 0;

    for (int i = 0; i < 8; i++) 
    {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if (nr >= 0 && nc >= 0 && nr < N && nc < M && map[nr][nc] != 0) dfs(nr,nc);
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    while(1)
    {
        cin >> M >> N;
        
        int island_cnt = 0;

        if (M == 0 && N == 0) break;

        for (int i = 0; i < N*M; i++) cin >> map[i/M][i%M]; 
        
        for (int i = 0; i < N*M; i++)
        {   
            int r = i/M;
            int c = i%M;

            if (map[r][c] != 0)
            {
                dfs(r,c);
                island_cnt++;
            }
        }

        cout << island_cnt << endl;

        memset(map, false, sizeof(map));
    }

    return 0;
}

 

 

3. Python

import sys


input = sys.stdin.readline

dr = [0,0,1,-1,1,-1,1,-1]
dc = [1,-1,0,0,1,-1,-1,1]

def dfs(r,c):
    stack = [(r,c)]
    island_map[r][c] = 0

    while stack:

        x,y = stack.pop()

        for i in range (0,8):
            nr = x + dr[i]
            nc = y + dc[i]

            if (nr >= 0 and nc >= 0 and nr < N and nc < M and island_map[nr][nc] != 0):
                stack.append((nr,nc))
                island_map[nr][nc] = 0  

while (True):
        
    island_cnt = 0
    M, N = map(int,input().split())

    if (N == M == 0):
        break
    
    island_map = [list(map(int, input().split())) for _ in range(N)]

    for i in range (0,N*M):
        if (island_map[i//M][i%M] != 0):
            dfs(i//M,i%M)
            island_cnt += 1


    print(island_cnt)

 

 

 

또한 BFS 알고리즘을 사용해서 해당 문제를 풀어줄 수 있다.

 

1. C++

#include <iostream>
#include <queue>
#include <utility>
#include <cstring> // use memset

using namespace std;

int N,M;
int map[50][50];
bool visited_map[50][50];
int dr[8] = {0,0,1,-1,1,-1,1,-1}; //행에 관한 방향데이터
int dc[8] = {1,-1,0,0,1,-1,-1,1}; //열에 관한 방향데이터


void bfs(int r, int c)
{
    queue<pair<int, int>> map_q;
    map_q.push(make_pair(r,c));
    visited_map[r][c] = true;

    while (!map_q.empty())
    {
        int cur_r = map_q.front().first;
        int cur_c = map_q.front().second;   
        map_q.pop();
        
        for (int i = 0; i < 8; i++) 
        {
            int new_r = cur_r + dr[i];
            int new_c = cur_c + dc[i];

            if (new_r >= 0 && new_c >= 0 && new_r < N && new_c < M && map[new_r][new_c] != 0 && !visited_map[new_r][new_c]) 
            {
                map_q.push(make_pair(new_r,new_c));
                visited_map[new_r][new_c] = true;
            } 
        }

    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    while(1)
    {
        cin >> M >> N;
        
        int island_cnt = 0;

        if (M == 0 && N == 0) break;

        for (int i = 0; i < N*M; i++) cin >> map[i/M][i%M]; 
        
        for (int i = 0; i < N*M; i++)
        {   
            int r = i/M;
            int c = i%M;

            if (map[r][c] != 0 && !visited_map[r][c])
            {
                bfs(r,c);
                island_cnt++;
            }
        }

        cout << island_cnt << endl;
        memset(map, false, sizeof(map));
        memset(visited_map, false, sizeof(visited_map));
    }

    

    return 0;
}

 

 

2. JAVA

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

public class Main {

    static int N,M;
    static int[][] map;
    static int[][] visitedMap;
    static int[] dr = {0,0,1,-1,1,-1,1,-1};
    static int[] dc = {1,-1,0,0,1,-1,-1,1};

    static class Pair {
        public int first;
        public int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

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

        while (true) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(stk.nextToken());
            N = Integer.parseInt(stk.nextToken());
            
            int islandCnt = 0;

            if (M == 0 && N == 0) break;
            
            map = new int[N][M];
            visitedMap = new int[N][M];

            for (int i = 0; i < N; i++) {
                stk = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(stk.nextToken());
            }

            for (int i = 0; i < N*M; i++) {
                int r = i/M;
                int c = i%M;

                if (map[r][c] != 0 && visitedMap[r][c] == 0) {
                    bfs(r, c);
                    islandCnt++;
                }
            }
            
            bw.write(islandCnt + "\n");
        }
        
        bw.close();
        br.close();
    }    
    
    static void bfs(int r, int c){
        
        visitedMap[r][c] = 1;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(r,c));
        
        while (!queue.isEmpty()) {
            
            int curR = queue.peek().first;
            int curC = queue.peek().second;
            queue.poll();  
            
            for (int i = 0; i < 8; i++) {
                int newR = curR + dr[i];
                int newC = curC + dc[i];
                
                if (newR >= 0 && newC >= 0 && newR < N && newC < M && map[newR][newC] != 0 && visitedMap[newR][newC] == 0) {
                    bfs(newR, newC);
                    visitedMap[newR][newC] = 1;
                }
            }
        }
    }
}

 

 

3. Python

import sys
from queue import Queue

input = sys.stdin.readline

dr = [0,0,1,-1,1,-1,1,-1]
dc = [1,-1,0,0,1,-1,-1,1]

def bfs(r,c):

    visited_map[r][c] = 1

    queue = Queue()
    queue.put((r,c))

    while not queue.empty():

        x,y = queue.get()

        for i in range (0,8):
            nr = x + dr[i]
            nc = y + dc[i]

            if (nr >= 0 and nc >= 0 and nr < N and nc < M and island_map[nr][nc] != 0 and visited_map[nr][nc] == 0):
                queue.put((nr,nc))
                visited_map[nr][nc] = 1  

while (True):
    
    island_cnt = 0
    M, N = map(int,input().split())

    if (N == M == 0):
        break   
    
    visited_map = [[0] * M for _ in range(N)]
    island_map = [list(map(int, input().split())) for _ in range(N)]

    for i in range (0,N*M):
        
        ind_r = i//M
        ind_c = i%M
        
        if (island_map[ind_r][ind_c] != 0 and visited_map[ind_r][ind_c] == 0):
            bfs(ind_r, ind_c)
            island_cnt += 1

    
    print(island_cnt)