문제#
- 링크로 대체
풀이 및 주저리..
백준 오프라인 수업 도중 설명을 듣고도 풀 때 어렵게 풀었던 문제이다. BFS 뿐만 아니라 Simulation 적인 요소도 잘 섞여 있는 문제라 나름 난이도가 꽤 높았던 문제였다. 그냥 단순하게 벽의 상하좌우에서 BFS 로 값을 구해주다보면 중복적인 부분이 너무 많고 연산시간이 엄청나게 오래걸려 시간 초과가 나는 문제이다. 그렇기 때문에 시작전에 빈곳을 이어 그룹화 시켜주고 그 다음 벽을 부수면서 진행하여 문제를 해결하였다.
코드가 깔끔하지 못해서 마음에 많이 걸리는데.. 아마 오프라인 수업중에 풀었던 문제를 한번 쭉 풀어본 뒤 다시 처음부터 쭉 풀어볼 예정이니, 다시 돌아올 때는 좀더 깔끔하게 풀 수 있는 실력이 되어있으면 좋을 것 같다.
먼저 일하는 날과 얻을 수 있는 수익을 배열로 만들어 저장해 두고 DPS 로 문제를 풀었다. 풀고나서 구글링 해보니 DP 로도 풀 수 있는 문제인 것 같은데, 좀 더 고민하고 후에 다시 도전해봐야겠다.
코드
package baekjoon.algorithm.day02;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
public class CrushWallAndMove4 {
static int[][] baseMap;
static int[][] answerMap;
static boolean[][] groupMap;
static ArrayList<Integer> arrGroupCnt = new ArrayList<>();
static char groupNum = 2;
static final int[][] DIR = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
static int N, M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
baseMap = new int[N][M];
answerMap = new int[N][M];
groupMap = new boolean[N][M];
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < line.length(); j++) {
int num = Character.getNumericValue(line.charAt(j));
baseMap[i][j] = num;
answerMap[i][j] = num;
}
}
makeGroup();
crushWall();
StringBuilder stb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
stb.append(answerMap[i][j]);
}
stb.append("\n");
}
System.out.println(stb.toString());
}
private static void makeGroup() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (baseMap[i][j] == 0) {
// 그룹화 시키기
int groupCnt = 0;
Queue<Integer> que = new LinkedList<Integer>();
groupMap[i][j] = true;
baseMap[i][j] = groupNum;
que.add(i);
que.add(j);
while (!que.isEmpty()) {
int x = que.poll();
int y = que.poll();
groupCnt++;
for (int k = 0; k < 4; k++) {
int tX = x + DIR[k][0];
int tY = y + DIR[k][1];
if (tX >= 0 && tX < N && tY >= 0 && tY < M) {
if (baseMap[tX][tY] == 0 && !groupMap[tX][tY]) {
groupMap[tX][tY] = true;
baseMap[tX][tY] = groupNum;
que.add(tX);
que.add(tY);
} else {
continue;
}
}
}
}
arrGroupCnt.add(groupCnt);
groupNum++;
}
}
}
}
private static void crushWall() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (baseMap[i][j] == 1) {
Set<Integer> temp = new HashSet<Integer>();
for (int k = 0; k < 4; k++) {
int tX = i + DIR[k][0];
int tY = j + DIR[k][1];
if (tX >= 0 && tX < N && tY >= 0 && tY < M && baseMap[tX][tY] != 1) {
temp.add(baseMap[tX][tY] - 2);
}
}
int sum = 1;
for (Integer integer : temp) {
sum += arrGroupCnt.get(integer);
}
answerMap[i][j] = sum % 10;
}
}
}
}
}기억에 남길 것!
- 문제를 시작전에 과연 내 풀이가 시간 복잡도를 계산하고 시작하자.
- 문제를 잘 읽고 자료구조를 어떻게 만들지 신중하게 생각해서 만들고 시작해야 후에 험한꼴을 보지 않는다..