구름톤 챌린지 20일차

문제

https://level.goorm.io/exam/195702/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C-%EC%A0%9C%EA%B1%B0%ED%95%98%EA%B8%B0/quiz/1

구름LEVEL

 

풀이

BFS 문제를 풀듯이 푸면 되는데 두가지 다른점이 있다.

1. 같은 숫자에 대해서 que에 넣는다는 것

2. list에 방문한 좌표를 넣는다는 것

 

1, 2를 시행하고 만약 같은 숫자들이 k개 이상이면 list에 저장한 좌표들을 바탕으로 board를 변경해주면 된다

 

코드

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

class Main {
	static char board[][];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		board = new char [n+1][n+1];
		
		for(int i=1;i<=n;i++){
			String str = br.readLine();
			for(int j=1;j<=n;j++){
				board[i][j] = str.charAt(j-1);
			}
		}
		
		for(int t=0;t<q;t++){
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			char ch = st.nextToken().charAt(0);
			
			board[y][x] = ch;
			

			bfs(n, k);
			
		}
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				System.out.print(board[i][j]);
			}
			System.out.println();
		}
	}
	
	static void bfs(int n, int k){
		int dx [] = {1, 0, -1, 0};
		int dy [] = {0, 1, 0, -1};
		
		boolean visited[][] = new boolean [n+1][n+1];
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(visited[i][j]) continue;
				Queue<int []> que = new LinkedList<>();
				List<int[]> list = new LinkedList<>();
				
				int count = 1;
				que.add(new int[]{i, j});
				list.add(new int[]{i, j});
				visited[i][j] = true;
				
				while(!que.isEmpty()){
					int cur[] = que.poll();
					
					for(int t=0;t<4;t++){
						int nx = cur[0] + dx[t];
						int ny = cur[1] + dy[t];
						
						if(nx < 1 || ny < 1 || nx > n || ny > n ) continue;
						if(visited[nx][ny]) continue;
						if(board[nx][ny] == board[cur[0]][cur[1]]){
							que.add(new int []{nx, ny});
							list.add(new int[]{nx, ny});
							visited[nx][ny] = true;
							count += 1;
						}
						
					}
					
				}
				if(count >= k){
					for(int t=0;t<list.size();t++){
						int pos [] = list.get(t);
						board[pos[0]][pos[1]] = '.';
					}
				}
			}
		}
	}
}