[SWEA] 7733. 치즈 도둑 (D4 / BFS) - Java

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWrDOdQqRCUDFARG&categoryId=AWrDOdQqRCUDFARG&categoryType=CODE&&& 

SW Expert Academy

 

 

 

문제 해석

N * N 짜리 크기의 치즈가 있고, 치즈의 위치에는 숫자가 정해져 있음

1~100일동안 날짜에 맞는 숫자를 먹음

 

1일부터 100일 동안 치즈를 먹으면서 나오는 덩어리 개수가 가장 많아지는 때의 덩어리 개수를 출력

 

 

 

코드

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

public class Solution {

	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };

	static int[][] map;
	static boolean[][] v;
	static int answer;

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

		int T = Integer.parseInt(st.nextToken());

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 한 변의 길이

			map = new int[N][N];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			answer = 0;

			for (int i = 0; i <= 100; i++) {
				v = new boolean[N][N]; // 반복 시 마다 초기화
				int nowCount = 0;
				for (int j = 0; j < map.length; j++) {
					for (int k = 0; k < map[0].length; k++) {
						if (map[j][k] == i) {
							map[j][k] = 0;
						}
					}
				}

				for (int j = 0; j < map.length; j++) {
					for (int k = 0; k < map[j].length; k++) {
						if (map[j][k] != 0 && v[j][k] == false) {
							bfs(j, k);
							nowCount++;
						}
					}
				}
				if (nowCount > answer) {
					answer = nowCount;
				}
			}

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case

	}

	static class Point {
		int x;
		int y;

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

	private static void bfs(int x, int y) {
		Queue<Point> q = new LinkedList<>();

		q.offer(new Point(x, y));
		v[x][y] = true;

		while (!q.isEmpty()) {
			Point p = q.poll();

			for (int i = 0; i < dx.length; i++) {
				int cx = p.x + dx[i];
				int cy = p.y + dy[i];

				if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length 
				&& v[cx][cy] == false
						&& map[cx][cy] != 0) {
					v[cx][cy] = true;
					q.offer(new Point(cx, cy));
				}
			}
		}

	}
}

 

 

 

코드 해석

덩어리를 구하는 문제 == bfs를 사용하는 문제입니다.

 

각 날짜마다 치즈를 먹고 덩어리를 구해야 하므로 방문을 표현하는 v[][] 배열을 사용하였습니다.

 

이외에는 기본적인 bfs를 0~100회까지 반복하는 동안 조건에 맞으면 bfs를 출력한다는 조건부만 차이가 있습니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice