문제

백준 4963번
https://www.acmicpc.net/problem/4963

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다..

---

생각하기

DFS/BFS 에서 처음으로 풀어보는 대각선으로 가는 문제였다.
물론 처음푼다고 어려운건 아니고, 그냥 평소에 풀던 상하좌우에서 아주 조금만 생각하면 쉽게 풀 수 있는 문제였다.

동작

	static int arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1 ,1, -1, 1, -1, 1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우
	static int dirY[] = {-1, 1, 0, 0, 1, 1, -1, -1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우

	static int w, h, nowX, nowY;

상 하 좌 우는 기존에 쓰던 배열과 똑같고,

뒤에오는 4개가 대각선을 탐색한다.

arr[x][y] 기준 대각선은 순서대로

• 상좌(위쪽 왼쪽 대각선) arr[1][-1]
• 상우(위쪽 오른쪽 대각선) arr[1][1]
• 하좌(아래쪽 왼쪽 대각선) arr[-1][-1]
• 하우(아래쪽 오른쪽 대각선) arr[-1][-1]

	static void DFS(int x, int y) {
		visit[x][y] = true;

		for(int i=0; i<8; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

			if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 1) {
				DFS(nowX, nowY);
			}
		}

	} // End of DFS

DFS와 BFS에서 탐색은 평소와 다르지 않았다.
단지 8개의 방향을 탐색하기 때문에 i 반복문이 8번의 반복을 한다는 점이 다르다는 것 뿐이다.

위 BFS 아래 DFS 큰 차이는 없었다.

---

코드

DFS

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

public class Main {
	static int arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1 ,1, -1, 1, -1, 1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우
	static int dirY[] = {-1, 1, 0, 0, 1, 1, -1, -1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우

	static int w, h, nowX, nowY;

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

		String str = " ";
		while( !(str = br.readLine()).equals("0 0") ) {
			st = new StringTokenizer(str);
	

			w = Integer.parseInt(st.nextToken()); // 너비
			h = Integer.parseInt(st.nextToken()); // 높이
			arr = new int[h][w];
			visit = new boolean[h][w];

			for(int i=0; i<h; i++) {
				st = new StringTokenizer(br.readLine());

				for(int j=0; j<w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
	
				}
			}

			int island_count = 0;
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {

					if(!visit[i][j] && arr[i][j] == 1) >
						island_count++;
						DFS(i, j);
					}
				}
			} 

			sb.append(island_count).append('\n');
		}

		System.out.println(sb);
	} // End of main

	static void DFS(int x, int y) {
		visit[x][y] = true;

		for(int i=0; i<8; i++) {
			nowX = dirX[i] + x;
			nowY = dirY[i] + y;

			if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 1) {
				DFS(nowX, nowY);
			}
		}

	} // End of DFS

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < h && nowY < w);
	} // End of range_check

} // End of Main class

---

BFS

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

public class Main {
	static int arr[][];
	static boolean visit[][];
	static int dirX[] = {0, 0, -1 ,1, -1, 1, -1, 1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우
	static int dirY[] = {-1, 1, 0, 0, 1, 1, -1, -1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우

	static int w, h, nowX, nowY;

	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

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

		String str = " ";
		while( !(str = br.readLine()).equals("0 0") ) {
			st = new StringTokenizer(str);


			w = Integer.parseInt(st.nextToken()); // 너비
			h = Integer.parseInt(st.nextToken()); // 높이
			arr = new int[h][w];
			visit = new boolean[h][w];

			for(int i=0; i<h; i++) {
				st = new StringTokenizer(br.readLine());

				for(int j=0; j<w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());

				}
			}

			int island_count = 0;
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					
					if(!visit[i][j] && arr[i][j] == 1) {
						BFS(i, j);
						island_count++;
					}
				}
			} 

			sb.append(island_count).append('\n');
		}

		System.out.println(sb);
	} // End of main
	
	static void BFS(int x, int y) {
		Queue<Node> que = new LinkedList<Node>();
		visit[x][y] = true;
		que.offer(new Node(x, y));
		
		while( !que.isEmpty() ) {
			Node node = que.poll();
		
			for(int i=0; i<8; i++) {
				nowX = dirX[i] + node.x;
				nowY = dirY[i] + node.y;

				if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 1) {
					visit[nowX][nowY] = true;
					que.offer(new Node(nowX, nowY));
				}
			}
		}

	} // End of BFS;

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < h && nowY < w);
	} // End of range_check
	
} // End of Main class