-
Java 2636 치즈PS 2023. 8. 22. 11:01
https://www.acmicpc.net/problem/2636
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
문제를 보고 치즈를 중심으로 공기와 닿는 지 아닌지를 체크하며 풀이를 하다가 문제에 가장자리에는 치즈가 놓일 수 없다는 조건을 다시 확인하였고 가장자리에서부터 녹는 치즈인지 아닌지를 체크하며 문제를 풀이하였다.
핵심 로직은 다음과 같다.
1. 초기 치즈 갯수를 카운트 해준 뒤 가장자리에서부터 상하좌우 bfs 탐색을 진행한다.
2. 치즈를 만난다면 해당 치즈는 녹는 치즈이므로 치즈 갯수를 빼준다.
3. 모든 치즈가 녹았다면 체크해둔 치즈 갯수와 진행한 횟수를 출력해준다.
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int r, c; static int[][] map; static boolean[][] visited; static int cheese; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); r = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); map = new int[r][c]; for (int i = 0; i < r; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) { map[i][j] = Integer.parseInt(st.nextToken()); if (map[i][j] == 1) { cheese++; } } } int remain = 0; int time = 0; while(cheese != 0){ remain = cheese; time++; visited = new boolean[r][c]; bfs(); } System.out.println(time); System.out.println(remain); } static void bfs(){ Queue<int[]> q = new LinkedList<>(); q.offer(new int[]{0, 0}); visited[0][0] = true; while(!q.isEmpty()){ int[] poll = q.poll(); for(int i = 0; i < 4; i++){ int nx = poll[0] + dx[i]; int ny = poll[1] + dy[i]; if(nx >= 0 && ny >= 0 && nx < r && ny < c && !visited[nx][ny]){ visited[nx][ny] = true; if(map[nx][ny] == 0){ q.offer(new int[]{nx,ny}); }else { cheese--; map[nx][ny] = 0; } } } } } }
'PS' 카테고리의 다른 글
Java 11967 불켜기 (0) 2023.08.25 Java 1655 가운데를 말해요 (0) 2023.08.25 Java 1976 여행 가자 (0) 2023.08.11 Java 11404 플로이드 (0) 2023.08.08 Java 16235 나무 재테크 (0) 2023.07.28