mingssssss

1. 문제

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

2. 코드

package mymain;

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

public class BOJ_4963 {
	
	static int[][] map;
	static boolean visited[][];
	static int[] dx = {-1 ,-1, -1, 0, 1, 1, 1, 0};
	static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while (true) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			// while문 종료조건
			if (N == 0 && M == 0) {
				break;
			} 
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			// 입력 끝
			int answer = 0;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					if (visited[i][j] == false && map[i][j] == 1) {
						BFS(i, j, M, N, visited, map);
						answer++;
					}
				}
			}
			System.out.println(answer);
			
		}
		
		
		
		
		
//		// 출력
//		for (int i = 0; i < map.length; i++) {
//			for (int j = 0; j < map[0].length; j++) {
//				System.out.printf("%d ", map[i][j]);
//			}
//			System.out.println();
//		}
		

	}
	
	public static void BFS (int r, int c, int M, int N, boolean[][] visited, int[][] map) {
		
		Queue<int[]> q = new LinkedList<>();
		visited[r][c] = true;
		q.add(new int[] {r, c});
		
		while (!q.isEmpty()) {
			
			int[] now = q.poll();
			
			for (int i = 0; i < 8; i++) {
				
				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];
				
				if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
					continue;
				}
				
				if (visited[nextX][nextY] == true || map[nextX][nextY] != 1) {
					continue;
				}
				
				visited[nextX][nextY] = true;
				q.add(new int[] {nextX, nextY});
								
			}
		}
		
		
		
		
	}

}

3. 리뷰

[백준] 11724_연결 요소의 개수와 비슷한 유형의 문제이다.

다만 이 문제는 노드와 간선이 주어진 것이 아니라 인접행렬이 주어졌다.

다른 문제와 다른 점은 입력의 개수가 정해져 있지 않아서 종료 조건을 따로 구현해야 한다는 것이다.

종료조건은 w, h 좌표에 각각 0이 들어가면 break로 while문을 빠져나오는 것으로 설정했다.

2차원 배열 map에 섬을 입력받고, 방문하지 않았으면서 동시에 1인 좌표를 BFS에 넣고 돌렸다.

8방향 탐색의 for문을 돌려서 해당 좌표가 섬 안에 있고, 방문하지 않았으면서 1이라면

해당 좌표를 방문처리하고 큐에 집어넣었다.

for문 하나가 끝났다면 연결된 모든 섬을 탐색했으므로 answer++ 해준다.

한 for문이 끝나고 다음 w, h의 좌표를 받아 각각 0이 아닐 때까지 while문을 돌렸다.

한번 bfs의 개념을 정리하고 나니 백준 실버 문제는 다 풀 수 있을 것 같다.

부지런히 남은 bfs 실버 문제를 푸려고 한다.