BEAKJOON / 백준 - JAVA 11123번 양 한마리... 양 두마리...

2024.08.20기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 그리드가 입력으로 주어 졌을 때 주어진 그리드에서 몇 무리의 양이 있는지를 출력하는 문제입니다.

 

1. 일단 BFS 검사를 하기 위해 여러가지 변수와 배열을 생성해줍니다.

static int h, w; // 그리드의 행과 열
static char[][] map; // 그리드를 저장하는 배열
static boolean[][] visit; // 확인을 했는지 체크해주는 배열
static int[] dx = {0, 1, 0, -1}; // x좌표의 위, 오른쪽, 아래, 왼쪽
static int[] dy = {-1, 0, 1, 0}; // y좌표의 위, 오른쪽, 아래, 왼쪽

 

2. 입력 받은 행과 열을 통해 map과 visit를 선언하고 그리드를 저장해줍니다.

st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken()); // 행
w = Integer.parseInt(st.nextToken()); // 열

map = new char[h][w]; // 그리드를 저장하는 배열
visit = new boolean[h][w]; // 확인을 했는지 체크하는 배열

for (int i = 0; i < h; i++) {
    str = br.readLine().toCharArray();

    for (int j = 0; j < w; j++) {
        map[i][j] = str[j];

        if (map[i][j] == '.') { // 풀이라면 true로 체크
            visit[i][j] = true;
        }
    }
}

 

3. 저장된 그리드를 통해 아직 확인하지 않은 양이라면 함수를 호출해 양의 무리를 체크해줍니다.

count = 0;
for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        if (!visit[i][j]) { // 양이면서 아직 숫자를 세지 않은 양이라면
            count++;
            function(i, j);
        }
    }
}

 

함수 호출

// 하나의 무리를 체크해주는 함수.
private static void function(int y, int x) {
    Queue<Integer> yq = new LinkedList<>();
    Queue<Integer> xq = new LinkedList<>();
    yq.add(y);
    xq.add(x);
    visit[y][x] = true;

    int nowy, nowx, nexty, nextx;
    while (!yq.isEmpty()) {
        nowy = yq.poll();
        nowx = xq.poll();

        // 상, 하, 좌우를 검사하기 위한 반복문
        for (int i = 0; i < 4; i++) {
            nexty = nowy + dy[i];
            nextx = nowx + dx[i];

            // 그리드를 벗어나지 않으면서 아직 카운터를 세지 않은 양이라면
            if (check(nexty, nextx) && !visit[nexty][nextx]) {
                visit[nexty][nextx] = true;

                // 그 양의 주변도 확인하기 위해 큐에 저장.
                yq.add(nexty);
                xq.add(nextx);
            }
        }
    }
}

// 그리드 범위 안인지 체크해주는 함수.
private static boolean check(int y, int x) {
    return x >= 0 && y >= 0 && x < w && y < h;
}

 

4. 이렇게 나온 양 무리 개수를 출력해줍니다.

 

 

코드

package Main;

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

public class Main {
	
	static int h, w;
	static char[][] map;
	static boolean[][] visit;
	static int[] dx = {0, 1, 0, -1}; // 위, 오른쪽, 아래, 왼쪽
	static int[] dy = {-1, 0, 1, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
		
		int count;
		char[] str;
		StringTokenizer st;
		
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			h = Integer.parseInt(st.nextToken()); // 행
			w = Integer.parseInt(st.nextToken()); // 열
			
			map = new char[h][w]; // 그리드를 저장하는 배열
			visit = new boolean[h][w]; // 확인을 했는지 체크하는 배열
			
			for (int i = 0; i < h; i++) {
				str = br.readLine().toCharArray();
				
				for (int j = 0; j < w; j++) {
					map[i][j] = str[j];
					
					if (map[i][j] == '.') { // 풀이라면 true로 체크
						visit[i][j] = true;
					}
				}
			}
			
			count = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (!visit[i][j]) { // 양이면서 아직 숫자를 세지 않은 양이라면
						count++;
						function(i, j);
					}
				}
			}
			
			sb.append(count).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 하나의 무리를 체크해주는 함수.
	private static void function(int y, int x) {
		Queue<Integer> yq = new LinkedList<>();
		Queue<Integer> xq = new LinkedList<>();
		yq.add(y);
		xq.add(x);
		visit[y][x] = true;
		
		int nowy, nowx, nexty, nextx;
		while (!yq.isEmpty()) {
			nowy = yq.poll();
			nowx = xq.poll();
			
			// 상, 하, 좌우를 검사하기 위한 반복문
			for (int i = 0; i < 4; i++) {
				nexty = nowy + dy[i];
				nextx = nowx + dx[i];
				
				// 그리드를 벗어나지 않으면서 아직 카운터를 세지 않은 양이라면
				if (check(nexty, nextx) && !visit[nexty][nextx]) {
					visit[nexty][nextx] = true;
					
					// 그 양의 주변도 확인하기 위해 큐에 저장.
					yq.add(nexty);
					xq.add(nextx);
				}
			}
		}
	}
	
	// 그리드 범위 안인지 체크해주는 함수.
	private static boolean check(int y, int x) {
		return x >= 0 && y >= 0 && x < w && y < h;
	}
}