[백준] Puyo Puyo

[hye-on]

🔗 Puyo Puyo

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; //11:39 vector>puyo(12,vector(6)); bool visit[12][6]; bool isPop; int h=-1; //높이 구하기 int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; bool OOB(int y,int x){ if(y>=12 || y<0 || x>=6 || x<0) return true; return false; } //bfs bool playPuyo(int y,int x,char Color){ queue>q; q.push({y,x}); visit[y][x] = true; int cnt=0; while(!q.empty()){ int curY = q.front().first; int curX = q.front().second; q.pop(); for(int i=0;i<4;i++){ int ny = curY + dy[i]; int nx = curX + dx[i]; if(OOB(ny,nx)) continue; if(!visit[ny][nx] && puyo[ny][nx]==Color){ q.push({ny,nx}); visit[ny][nx] = true; cnt++; } } } // cout<=3){ //visit true 인것 .으로 만들기 for(int i=h;i<12;i++){ for(int j=0;j<6;j++){ if(visit[i][j]){ puyo[i][j]='.'; } } } return true; } else{ for(int i=h;i<12;i++){ for(int j=0;j<6;j++){ visit[i][j]=false; } } return false; } } void gravitation(){ for(int j=0;j<6;j++){ for(int i = 11;i>=h;i--){ if(puyo[i][j]!='.'){ int y = i+1; while(y<12 && puyo[y][j]=='.'){ puyo[y][j] = puyo[y-1][j]; puyo[y-1][j]='.'; y++; } } } } } int main() { string tmp=""; for(int i=0;i<12;i++){ cin>>tmp; int t=0; for(int j=0;j<6;j++){ puyo[i][j]=tmp[j]; if(tmp[j]=='.') t++; } } for(int i=0;i<12;i++){ for(int j=0;j<6;j++){ if(puyo[i][j]!='.'){ h=i; break; } } if(h>=0) break; } int answer=0; if(h < 0) h = 0; while(true){ for(int i=h;i<12;i++){ for(int j=0;j<6;j++){ if(puyo[i][j]!='.' && !visit[i][j]){ if(playPuyo(i,j, puyo[i][j])){ isPop =true; } } } } //visit 초기화 memset(visit,false,sizeof(visit)); gravitation(); if(isPop) answer++; else break; isPop=false; } cout<

코멘트

- 어렵진 않았는데 빨리 풀진 못했네요. .처리를 해주는 시점이 효율적인지 모르겠습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 20:00 시작! */ public class Main { static char[][] snapshot; static Deque[] map; public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); map = new Deque[6]; for(int i = 0; i < 6; ++i) map[i] = new ArrayDeque<>(); snapshot = new char[6][12]; // map[i][j]는 i열의 j행 아래가 0행! for(int i = 0; i < 12; ++i) { String line = bf.readLine(); char[] chars = line.toCharArray(); for(int j = 0; j < 6; ++j) { snapshot[j][i] = chars[j]; map[j].offer(chars[j]); } } int count = 0; while(hasBomb()) { // 터질 뿌요들이 있다면? bomb(); count++; } System.out.println(count); } static boolean[][] toRemove; static boolean[][] visit; public static boolean hasBomb() { boolean hasBomb = false; toRemove = new boolean[6][12]; // 제거해야 하는 뿌요 visit = new boolean[6][12]; for(int i = 0; i < 6; ++i) { for(int j = 0; j < 12; ++j) { if(snapshot[i][j] == '.' || visit[i][j]) continue; boolean[][] connect = new boolean[6][12]; int count = check(i, j, connect); // 얘랑 연결된 애들이 4개 이상인지 확인! if(count >= 4) { hasBomb = true; mark(connect, toRemove); } } } return hasBomb; } static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; public static int check(int col, int row, boolean[][] connect) { connect[col][row] = true; visit[col][row] = true; int total = 1; for(int d = 0; d < 4; ++d) { int nCol = col + dx[d]; int nRow = row + dy[d]; if(nCol >= 0 && nCol < 6 && nRow >= 0 && nRow < 12 && !connect[nCol][nRow] && snapshot[nCol][nRow] == snapshot[col][row]) { total += check(nCol, nRow, connect); } } return total; } public static void mark(boolean[][] connect, boolean[][] toRemove) { for(int i = 0; i < 6; ++i) { for(int j = 0; j < 12; ++j) { if(connect[i][j]) { toRemove[i][j] = true; } } } } public static void bomb() { for(int i = 0; i < 6; ++i) { Deque deque = new ArrayDeque<>(); for(int j = 0; j < 12; ++j) { Character puyo = map[i].poll(); if(!toRemove[i][j]) { deque.offer(puyo); } } while(deque.size() < 12) { deque.offerFirst('.'); } for(int j = 0; j < 12; ++j) { Character puyo = deque.poll(); snapshot[i][j] = puyo; deque.offer(puyo); } map[i] = deque; } } } ```

코멘트

- 빡 구현 문제 였던 것 같습니당.. 삭제 비용을 줄이기 위해서 큐 자료구조를 사용했습니다!