[Baekjoon] 28256_초콜릿 보관함

문제(출처: https://www.acmicpc.net/problem/28256)

---

< 초콜릿 보관함 >

 

문제 풀이 

 

초콜릿이 있는 곳에서 상하좌우를 탐색하여 초콜릿이 연결되어 있는지 확인한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _28256_ { // 초콜릿 보관함
	static char arr[][];
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

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

		int T = Integer.parseInt(bf.readLine());

		for (int i = 0; i < T; i++) {
			arr = new char[3][3];
			visited = new boolean[3][3];
			for (int j = 0; j < 3; j++) {
				String str = bf.readLine();
				for (int k = 0; k < 3; k++) {
					arr[j][k] = str.charAt(k);
				}
			}

			ArrayList<Integer> result = new ArrayList<>();
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if (arr[j][k] == 'O' && !visited[j][k]) {
						visited[j][k] = true;
						result.add(search(j, k, 1));
					}
				}
			}

			Collections.sort(result);

			st = new StringTokenizer(bf.readLine());
			int num = Integer.parseInt(st.nextToken());
			int answer[] = new int[num];
			boolean flag = false;
			for (int j = 0; j < num; j++) {
				answer[j] = Integer.parseInt(st.nextToken());
			}

			if (result.size() != num) {
				bw.write("0\n");
			} else {
				for (int j = 0; j < num; j++) {
					if (result.get(j) != answer[j]) {
						bw.write("0\n");
						flag = true;
						break;
					}
				}
				if (!flag) {
					bw.write("1\n");
				}
			}
		}
		bw.flush();
	}

	private static int search(int a, int b, int cnt) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { a, b });

		while (!queue.isEmpty()) {
			int info[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = info[0] + dx[i];
				int y = info[1] + dy[i];
				if (x >= 0 && x < 3 && y >= 0 && y < 3 && arr[x][y] == 'O' && !visited[x][y]) {
					visited[x][y] = true;
					cnt += 1;
					queue.add(new int[] { x, y });
				}
			}
		}
		return cnt;
	}
}

변수)
T : 테스트 케이스의 개수
arr : 초콜릿 보관함 상태
visited : 방문 여부
result : 초콜릿 보관함 결과
num : 화면에 표시된 숫자의 개수
answer : 화면에 표시된 숫자 정보
flag : 일치 여부

 

테스트 케이스 개수를 입력받는다. 테스트 케이스 수만큼 다음 과정을 반복한다.

 

1) 초콜릿 보관함 상태를 입력받아 arr에 저장한다.

2) 초콜릿 보관함을 살펴보며 초콜릿이 있다면 search 함수를 호출한다. 반환값을 result에 저장한다.

3) result를 오름차순으로 정렬한다.

4) 화면에 표시된 숫자를 입력받고, 그 수만큼 숫자를 입력받아 answer 배열에 저장한다.

5) result와 answer을 비교하며 일치하면 1을 일치하지 않다면 0을 출력한다.

 

search(초콜릿 위치, 1)

Queue에 초콜릿 현재 위치를 저장한다. Queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue에서 값 꺼내기

2) 상하좌우를 탐색하며 초콜릿이 있고 아직 방문하지 않은 곳이라면 방문 후 cnt+1 및 queue에 위치 저장

 

cnt 반환

---

---