[SWEA JAVA] 7733번: 치즈 도둑

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWrDOdQqRCUDFARG.

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, ans = 0, max = 0;
	public static int[][] map = new int[100][100];
	public static int[][] visited;
	public static List<int[]>[] list;
	public static int[] dx = { -1, 0, 1, 0 };
	public static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			ans = 0;
			max = 0;
			list = new ArrayList[101];
			for(int i = 0; i< 101;i++ ) {
				list[i] = new ArrayList<>();
			}
			
			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());
					if (map[i][j] > max) {
						max = map[i][j];
					}
					list[map[i][j]].add(new int[] {i,j});
				}
			}

			for (int idx = 0; idx <= max; idx++) {
				for (int[] cur : list[idx]) {
					map[cur[0]][cur[1]] = 0;
				}
				int cnt = Sol();
				if(cnt > ans) {
					ans = cnt;
				}
			}

			System.out.println("#" + tc + " " + ans);
		}
	}

	public static int Sol() {
		visited = new int[N][N];
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0 && visited[i][j] == 0) {
					visited[i][j] = 1;
					bfs(i, j);
					cnt++;
				}
			}
		}
		
		return cnt;

	}

	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { x, y });
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if(nx >= 0 && nx < N && ny >= 0 && ny < N) {
					if(map[nx][ny] > 0 && visited[nx][ny] == 0) {
						visited[nx][ny] = 1;
						q.offer(new int[] {nx, ny});
					}
				}
			}
		}
	}
}

 

0일차에 계산한 값도 넣어줘야 한다.

 

풀이 사항
풀이 일자: 2024.08.26
풀이 시간: 70분 00초
채점 결과: 정답
예상 문제 유형: DFS, BFS

 

풀이 방법

단지 번호 붙이기랑 비슷하다고 생각했다. 1. 맛있는 정도가 바뀔때마다 맵을 전부 돌며 해당 값에 맞는지 안맞는지 확인하는 방법이 싫어서 맛있는 정도가 1부터 100까지 주어지므로 리스트를 100개 만들어서 해당 맛있는 정도 값이 들어있는 x, y 좌표를 리스트에 넣어주었다.2. 1부터 가장 맛있는 정도인 max 까지 for 문을 돌며 map에 그 값을 0으로 바꿔주었다.3. BFS를 돌며 덩어리의 갯수를 세준다.4. ans와 비교하여 더 큰값을 넣어주고 2~4를 반복한다.

 

여기서 테케가 11개중에 10개만 맞게되었다.

 

이유를 찾아보니 0일차도 계산해 주어야한다는 댓글을 보고 위에 2번을 0부터 진행해 주었고 통과되었다.

 

테케가 여러개 중에 몇개만 다르다면 배열의 범위를 확인해보자.