[Java] 프로그래머스(level-2) - 프렌즈4블록
문제 풀이
이번 문제는 문제에서 요구한 대로 구현하기만 하면 되는 문제이다.
아이디어 도출
문제의 요구사항대로 정리하면 아이디어는 간단하다.
- 2X2 블록을 체크한다.
- 체크된 2x2 블록을 제거한다. 블록의 제거는 ‘#’으로 치환하는 것으로 한다.
- 블록을 떨어뜨린다.
- 제거할 블록이 없을 때까지 1-3번 과정을 반복한다.
2X2 블록을 체크하고 제거하는 것은 크게 어렵지 않았지만, 블록을 떨어뜨리는(윗블록과 아랫블록을 교체하는) 작업에서 배열을 잘 다룰 수 있어야 함을 느꼈다.
블록을 떨어뜨릴 때는 board를 탐색하면서 3중 for문을 이용해 세로 열로 제거된 블록과 제거되지 않은 블록을 교체하도록 구현하였다.
다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.util.*;
class Solution {
// 1. 2X2 블록을 체크한다.
// 2. 체크된 2x2 블록을 제거한다. 블록의 제거는 '#'으로 치환하는 것으로 한다.
// 3. 블록을 떨어뜨린다.
// 4. 제거할 블록이 없을 때까지 1-3번 과정을 반복한다.
static boolean[][] visited;
static char[][] map;
public int solution(int m, int n, String[] board) {
map = new char[m][n];
for(int i=0; i<m; i++) {
String input = board[i];
for(int j=0; j<n; j++) {
map[i][j] = input.charAt(j);
}
}
// 제거된 블록의 수를 담기 위해 0으로 초기화
int answer = 0;
while(true) {
boolean isContinue = true;
visited = new boolean[m][n];
for(int i=0; i<m-1; i++) {
for(int j=0; j<n-1; j++ ) {
// 이미 지워진 블록은 체크할 필요가 없다.
if(map[i][j] == '#') {
continue;
}
// 현재 위치부터 2X2 블록이 같다면 체크해둔다.
if(checkBlock(i, j)) {
visited[i][j] = true;
visited[i][j+1] = true;
visited[i+1][j] = true;
visited[i+1][j+1] = true;
isContinue = false;
}
}
}
// 종료조건: 제거할 블록이 없다면 종료한다.
if(isContinue) {
break;
}
// 지워진 블록의 수를 담는다.
answer += removeBlock(m, n);
// 블록 제거 후 위에 있는 블록을 떨어뜨린다.
dropBlock(m, n);
}
System.out.println(answer);
return answer;
}
// 현재 위치의 블록으로부터 오른쪽, 아래, 오른쪽 아래 블록이 같은 블록인지 확인하는 함수
static boolean checkBlock(int x, int y) {
char block = map[x][y];
if(block == map[x][y+1] && block == map[x+1][y] && block == map[x+1][y+1]) {
return true;
}
return false;
}
// 블록을 '#'으로 치환해 제거한다.
static int removeBlock(int m, int n) {
int cnt = 0;
// 블록을 제거하면서 제거된 블록의 수 카운트
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(visited[i][j]) {
map[i][j] = '#';
cnt++;
}
}
}
return cnt;
}
static void dropBlock(int m, int n) {
for(int i=0; i<n; i++) {
for(int j=m-1; j>=0; j--) {
// '#' 로 제거된 블록만 위로 올린다.
if(map[j][i] == '#') {
// 세로로 탐색하며 제거된 블록을 스왑하여 위의 블록을 아래로 내린다.
for(int k=j-1; k>=0; k--) {
if(map[k][i] == '#') {
continue;
}
map[j][i] = map[k][i];
map[k][i] = '#';
break;
}
}
}
}
}
public static void main(String[] args) {
Solution sol = new Solution();
// int m = 6;
// int n = 6;
// String[] board = new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
int m = 4;
int n = 5;
String[] board = new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"};
sol.solution(m, n , board);
}
}
회고
-
출처
-
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.