BOJ9441 Cash Cow

<문제요약>

https://www.acmicpc.net/problem/9441

9441번: Cash Cow

1. B 파란색, R 빨간색, Y 노란색
2. 클러스터 : 색상이 일치하는 수평 수직 이웃
3. 표시된 그리드 셀이 하나 또는 두 개의 원이 있는 클러스터에 속해 있으면(또는 해당 셀에 원이 없는 경우) 회전이 낭비됩니다.
그렇지 않으면 3개 이상의 원이 있는 클러스터에서 클러스터의 모든 원이 보드에서 제거됩니다. -> 클러스터는 3개 이상??
4. 압축
(1) 원이 세로로 떨어지며 기둥의 구멍을 채움
(2) 하나 이상의 열이 비어 있으면 나머지 열은 모두 왼쪽으로 미끄러져 보드의 왼쪽 가장자리에 채워짐

<풀이 흐름, Source Code>

1. 클러스터 찾기 BFS char[][] 배열로 map 표시
(1) 클릭된 색의 인접한 같은 색을 bfs큐에 넣어서 인접한 모든 같은 색의 위치를 기록한다. remove_q에 저장
(2) BFS가 끝나면 몇 개가 인접했는지 보고 3개이상 이면 위치에 기록된 곳을 다 E로 만들어준다

2. 압축
(1) 세로 스왑
한 열에서 E에 개수를 카운트하고 카운트된 만큼 아래에서 위로 스왑을 해준다
(2) 가로 스왑
세로 스왑이 다 끝나고 마지막 행에 E가 있는 경우라면 해당 열 전체가 E라는 의미, 그러한 열을 카운트 해주고
카운트된 만큼 왼쪽에서 오른쪽으로 스왑 해준다.

3. 최종 E 개수 카운트해서 print

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ9441_CashCow {
	
	static int T;
	static char[][] map;
	static boolean[][] visited;
	static int row, col;
	static int[] arrx = {0,1,0,-1}, arry = {-1,0,1,0};
	static Queue<node> remove_q = new LinkedList<node>();
	static int[] arr_row = {0,11,10,9,8,7,6,5,4,3,2,1,0};
	
	private static class node{
		int x;
		int y;
		node(int x,int y){
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		input();
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = -1;
		while(T != 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			T = Integer.parseInt(st.nextToken());
			if(T == 0)
				return;
			map = new char[12][10];
			
			for(int i = 0; i < 12; i++) {
				String str = br.readLine();
				for(int j = 0; j < 10; j++) {
					map[i][j] = str.charAt(j);
				}
			}
			
			for(int ti = 0; ti < T; ti++) {
				st = new StringTokenizer(br.readLine(), " ");
				col = st.nextToken().charAt(0) - 'a';
				row = arr_row[Integer.parseInt(st.nextToken())]; // 문제에서의 row랑 내가 생각한거랑 반대
				run();
			}
			print();
		}
	}
	
	private static void run() {
		int cluster_result = cluster();
		if(cluster_result == 1)
			press();
	}
	
	private static int cluster() {
		if(map[row][col] != 'E') {
			bfs();
			remove();
			return 1;
		}
		else
			return 0;
	}
	
	private static void bfs() {
		Queue<node> q = new LinkedList<node>();
		remove_q = new LinkedList<node>();
		q.add(new node(row,col));
		remove_q.add(new node(row,col));
		visited = new boolean[12][10];
		visited[row][col] = true;
		while(!q.isEmpty()) {
			node n = q.poll();
			for(int di = 0; di < 4; di++) {
				int dx = n.x + arrx[di];
				int dy = n.y + arry[di];
				if(dx >= 0 && dx < 12 && dy >= 0 && dy < 10 && !visited[dx][dy]) {
					visited[dx][dy] = true;
					if(map[dx][dy] == map[row][col]) {
						q.add(new node(dx,dy));
						remove_q.add(new node(dx,dy));
					}
				}
			}
		}
	}
	
	private static void remove() {
		if(remove_q.size() >= 3) {
			while(!remove_q.isEmpty()) {
				node n = remove_q.poll();
				map[n.x][n.y] = 'E'; 
			}
		}
	}
	
	private static void press() {
		col_press();
		row_press();
	}
	
	private static void col_press() {
		int E_cnt = 0;
		for(int icol = 0; icol < 10; icol++) {
			for(int row = 0; row < 12; row++) {
				if(map[row][icol] == 'E')
					E_cnt++;
			}
			
			for(int irow = 0; irow < E_cnt; irow++) {
				for(int row = 11; row > 0; row--) {
					if(map[row][icol] == 'E') {
						char temp = map[row-1][icol];
						map[row-1][icol] = map[row][icol];
						map[row][icol] = temp;
					}
				}
			}
		}
	}
	
	private static void row_press() {
		int E_cnt = 0;
		for(int icol = 0; icol < 10; icol++) {
			if(map[11][icol] == 'E')
				E_cnt++;
		}
		
		for(int icnt = 0; icnt < E_cnt; icnt++) {
			for(int icol = 0; icol < 9; icol++) {
				if(map[11][icol] == 'E') {
					for(int row = 11; row >= 0; row--) {
						char temp = map[row][icol+1];
						map[row][icol+1] = map[row][icol];
						map[row][icol] = temp;
					}
				}
			}
		}
	}

	private static void print() {
		int result = 0;
		for(int i = 0; i < 12; i++) {
			for(int j = 0; j < 10; j++) {
				if(map[i][j] != 'E')
					result++;
			}
		}
		System.out.print(result + "\n");
	}
}

<문제 Issue>

1. 문제에서의 row, col을 잘 생각해서 map 탐색 필요! 헷갈리지 않게 처음부터 정의랑 딱 잡고 시작

<중요 정리>

X