[SWEA 5656] 벽돌 깨기(JAVA/C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

 

 

 

재귀를 이용해서 N번까지 구슬을 쏴주고, 큐를 이용해서 블록 깨기, 맵이동을 시켜줬다.

맵이동시킬 때 H를 N으로 오타내서 시간을 낭비했다.. 자잘한 실수를 조심하자!

 

[JAVA]

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

class Point {
	int x;
	int y;

	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

}

public class Solution_5656_벽돌깨기 {

	static int N, W, H, ans;// 횟수 가로 세로
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			ans = 987654321;
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			map = new int[H][W];
			for (int i = 0; i < H; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			solve(0);
			if(ans==987654321) ans=0;
			System.out.println("#" + tc + " " + ans);
		}

	}

	private static void solve(int cnt) {
		if (cnt == N) {
			// 남은 벽돌 세기
			int result = 0;
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if (map[i][j] > 0)
						result++;
				}
			}
			if (ans > result)
				ans = result;
			return;
		}
		int[][] copy = new int[H][W];
		mapCopy(copy, map);

		for (int k = 0; k < H; k++)for (int c = 0; c < W; c++) {
			copy[k][c] = map[k][c];
		}
		for (int j = 0; j < W; j++) {
			for (int i = 0; i < H; i++) {
				if (map[i][j] > 0) {
					breaking(i, j);
					move();
					solve(cnt + 1);
					mapCopy(map, copy);
					break;
				}
			}
		}

	}

	private static void move() {
		for (int j = 0; j < W; j++) {
			Queue<Integer> q = new LinkedList<Integer>();
			for (int i = H - 1; i >= 0; i--) {
				if (map[i][j] > 0) {
					q.offer(map[i][j]);
					map[i][j] = 0;
				}
			}
			int i = H - 1;
			while (!q.isEmpty()) {
				map[i][j] = q.poll();
				i--;
			}
		}
	}

	private static void breaking(int x, int y) {
		visit = new boolean[H][W];
		Queue<Point> q = new LinkedList<Point>();
		visit[x][y] = true;
		q.offer(new Point(x, y));
		while (!q.isEmpty()) {
			Point p = q.poll();
			int val = map[p.x][p.y] - 1;
			map[p.x][p.y] = 0;
			if (val > 0) {
				for (int i = 0; i < 4; i++) {
					for (int c = 1; c <= val; c++) {
						int nx = p.x + dx[i] * c;
						int ny = p.y + dy[i] * c;

						if (nx < 0 || ny < 0 || nx >= H || ny >= W || map[nx][ny] == 0 || visit[nx][ny] == true)
							continue;
						visit[nx][ny] = true;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}

	}

	private static void mapCopy(int[][] copy, int[][] origin) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				copy[i][j] = origin[i][j];
			}
		}

	}

}

 

 

[C++]

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N, W, H; //W열 H행
int ans;
int map[15][12];

bool visited[15][12];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

void Move() {
	
	for (int j = 0; j < W; j++) {
		queue <int> q;
		for (int i = H - 1; i >= 0; i--) {
			if (map[i][j]) {
				q.push(map[i][j]);
				map[i][j] = 0;
			}
		}
		int index = H - 1;
		while (!q.empty()) {
			int val = q.front();
			q.pop();
			map[index][j] = val;
			index--;
		}
	}
	
	
}
void Breaking(int i, int j) {

	memset(visited, 0, sizeof(visited));
	queue <pair<int, int> > q;
	visited[i][j] = true;
	q.push({ i,j });
	int cnt = 0;
	int val = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		val = map[x][y];
		map[x][y] = 0; //벽돌 깨뜨리기
		
		
		if (val > 1) {
			cnt = val - 1;
			for (int i = 0; i < 4; i++) {
				for (int z = 1; z <= cnt; z++) {
					int nx = x + dx[i] * z;
					int ny = y + dy[i] * z;
					if (nx < 0 || ny < 0 || nx >= H || ny >= W || map[nx][ny] == 0 || visited[nx][ny])
						continue;
					visited[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}

}
void Solve(int cnt) {
	if (cnt == N) {
		int res = 0;
		for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
			if (map[i][j] > 0)res++;
		}
		if (res < ans)ans = res;
		return;
	}
	
	//구슬 쏘기
	//맵복사
	int cmap[15][12];
	for (int k = 0; k < H; k++)for (int c = 0; c < W; c++) {
		cmap[k][c] = map[k][c];
	}
		for (int j = 0; j < W; j++) {	
			for (int i = 0; i < H; i++) {
				if (map[i][j]) {			
					Breaking(i, j);
					Move();
					Solve(cnt + 1);
					//맵복구
					for (int k = 0; k < H; k++)for (int c = 0; c < W; c++) {
						map[k][c] = cmap[k][c];
					}
					break;
				}
			}

		}
	

	
	
}
int main() {
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		ans = 987654321;
		cin >> N >> W >> H;
		for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
			cin >> map[i][j];
			
		}
		
			Solve(0);
			if (ans == 987654321) ans = 0;
		cout << "#" << tc << " " << ans << '\n';
	}
	return 0;
}