백준 1926번 : 그림

문제 풀이

• 접근법 : BFS, Flood Fill
  한 점에서 시작되는 각각의 그림을 BFS를 이용해 파악해낸다.

• 풀이 과정

  1. 모든 배열 원소에 대해 아래 과정을 반복한다.
  2. 원솟값이 만약 1이고 아직 방문하지 않았으면 큐에 원소(좌표)를 삽입하고, 방문했다는 표시를 남긴다.
  3. 큐가 비어있지 않다면, 첫 번째 원소를 꺼내고 해당 그림의 크기를 1 증가시킨다.
     그리고 해당 원소의 인접한 원소에 대해 오른쪽, 위쪽, 왼쪽, 아래쪽 순서대로 '2번'을 반복 수행한다.
  4. '3번'을 큐가 빌 때까지 반복한다.
  5. '4번' 반복문에서 탈출하면 그림의 개수를 1 증가시킨다.
     ⇒ 하나의 원소로부터 시작된 한 그림을 파악해낸 것!

java 구현 코드

package ch08_BFS;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class p1926 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();  // 도화지의 세로 크기 n
		int m = sc.nextInt();  // 도화지의 가로 크기 m
		
		int[][] pictureArr = new int[n + 2][m + 2];  // 그림 배열
		int[][] visited = new int[n + 2][m + 2];  // 처리 여부 저장 배열
		
		int[] dx = {1, 0, -1, 0};  // 우 상 좌 하
		int[] dy = {0, 1, 0, -1};
		
		for (int i = 1; i <= n; i++) {  // 그림 배열값 세팅
			for (int j = 1; j <= m; j++) {
				pictureArr[i][j] = sc.nextInt();
			}
		}
		
		
		Queue<Pair> queue = new LinkedList<>();  // 큐 생성
		int count = 0;  // 그림의 개수
		int maxSize = 0;  // 그림의 최대 크기
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				
				if (pictureArr[i][j] == 1 && visited[i][j] == 0) {  // 시작 좌표가 그림이고, 아직 방문하지 않았으면
					int size = 0;  // 그림의 크기
					
					queue.add(new Pair(i, j));  // 큐에 삽입
					visited[i][j] = 1;  // 방문 완료 갱신
					
					while (!queue.isEmpty()) {  // 큐가 비어있지 않으면 (큐가 빌 때까지 반복)
						Pair pair = queue.remove();  // 큐에서 front 좌표를 꺼내고
						size++;  // 해당 그림의 크기 갱신
						
						for (int d = 0; d < 4; d++) {  // 해당 좌표의 주변 좌표를 우상좌하 순으로 탐색 
							int tmpX = pair.X + dx[d];  // 주변 좌표 : (tmpX, tmpY)
							int tmpY = pair.Y + dy[d];
							
							if (pictureArr[tmpX][tmpY] == 1 && visited[tmpX][tmpY] == 0) {  // 그림이고, 아직 방문하지 않았으면
								queue.add(new Pair(tmpX, tmpY));  // 큐에 해당 좌표 삽입
								visited[tmpX][tmpY] = 1;  // 방문 완료 갱신
							}
						}
					}
					count++;  // 그림의 개수 갱신
					if (size > maxSize) maxSize = size;  // 그림의 최대 크기 갱신
				}
			}
		}
		
		System.out.println(count + "\n" + maxSize);

	}

}

class Pair {  // 좌표 값을 저장할 자료구조 Pair 
	int X;
	int Y;
	
	Pair(int x, int y) {
		this.X = x;
		this.Y = y;
	}
}

문제 해결

값 갱신의 잘못된 시점으로 버그 발생

size값이 자꾸 크게 나오는 버그가 발생했다.
한시간 넘게 똑같은 코드를 바라보고 있던 결과,,, visited 배열값 갱신 시점에 문제가 있음을 발견했다.
이전에 버그가 발생한 코드는 아래와 같다.

for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				
				if (pictureArr[i][j] == 1 && visited[i][j] == 0) {  // 시작 좌표가 그림이고, 아직 방문하지 않았으면
					int size = 0;  // 그림의 크기
					
					queue.add(new Pair(i, j));  // 큐에 삽입
					
					while (!queue.isEmpty()) {  // 큐가 비어있지 않으면 (큐가 빌 때까지 반복)
						Pair pair = queue.remove();  // 큐에서 front 좌표를 꺼내고
						
						for (int d = 0; d < 4; d++) {  // 해당 좌표의 주변 좌표를 우상좌하 순으로 탐색 
							int tmpX = pair.X + dx[d];  // 주변 좌표 : (tmpX, tmpY)
							int tmpY = pair.Y + dy[d];
							
							if (pictureArr[tmpX][tmpY] == 1 && visited[tmpX][tmpY] == 0) {  // 그림이고, 아직 방문하지 않았으면
								queue.add(new Pair(tmpX, tmpY));  // 큐에 해당 좌표 삽입
							}
						}
						size++;  // 해당 그림의 크기 갱신
						visited[pair.X][pair.Y] = 1;  // 방문 완료 갱신
					}
					count++;  // 그림의 개수 갱신
					if (size > maxSize) maxSize = size;  // 그림의 최대 크기 갱신
				}
			}
		}

큐에서 꺼낸 원소(좌표)를 a라 하자.
만약 visited[pair.X][pair.Y] = 1; 이 라인을 위 코드처럼 a의 인접한 원소 4개를 탐색 완료한 후에 수행하게 되면 a가 큐에 여러 번 들어가게 되어 size++; 라인이 필요 이상으로 수행되게 된다.
따라서, visited[pair.X][pair.Y] = 1; 라인을 큐에 원소를 삽입할 때 같이 수행해주어야 한다.

Comment

풀이 날짜 : 2023/12/20 (수)

바킹독 BFS 강의를 듣고 파이썬 샘플 코드를 참고하여 처음으로 스스로 구현한 BFS 문제이다.
알고리즘 문제를 단순히 코드로 구현하는 것에서 그치지 않고, 남에게 문제를 설명하고, 문제풀이 접근 방법과 내가 구현한 코드에 대해 설명할 수 있도록 실력을 키우는 것이 나의 알고리즘 공부 목표이다.
1월에는 알고리즘 스터디에 참여해볼 계획이다. 내 코드를 남들에게 공유해도 부끄럽지 않을 수 있게, 남은 12월 동안 얼른 개념 공부 끝내고 문제 많~이 풀어야겠다. 파이팅 !