Algorithm/Problem_SW
SW 역량 테스트 기출 문제(구슬 탈출 2, 2048 easy)
uyoo
2019. 10. 7. 01:18
[구슬 탈출 2 _ 13460]
* 조건
1. 보드를 4개의 방향으로 기울일 때, RedBall과 BlueBall이 동시에 해당 방향으로 기울어져야 함
2. 기울이는 사이클동안 파란공이 탈출하게 되면 실패
3. RedBall과 BlueBall은 겹칠 수 없음
4. 최대 10번까지 움직일 수 있음
* 알고리즘
- 인접한 길을 통해서 이동: BFS
- 4개 방향(상,하,좌,우)을 고려해 이동되는 경우의 수를 탐색 및 최소 횟수 찾기 : 브루트포스
* 로직(Logic)
- RedBall과 BlueBall의 위치를 한 번에 담아주는 클래스를 생성하고 해당 위치를 담아줌
- 시계방향으로 보드를 기울이기
- 기울여서 각 공이 이동할 때, 벽('#')에 닿거나 목적지('O')에 닿으면 이동을 멈춤
- 각 공마다 이동할 때 소요되는 거리(칸 개수)를 통해 RedBall과 BlueBall이 동일 위치에 겹치는 상황을 방지
ex. 만약 RedBall이 이동할때 4칸이 소요되고 BlueBall이 3칸 소요된다면 BlueBall 뒤 or 옆에 RedBall을 배치해야 함
(조건-3 처리)
- 움직인 횟수(count)가 > 10 이면 -1
- 이동되는 사이클 수행 도중 BlueBall이 목적지에 있다면 큐에 넣지 않음 / 없다면 큐에 넣고 체크
(중복 방지 및 4개 방향의 모든 경우의 수를 고려하기 위해 checked[][][][] 4차원 배열로 마킹)
- RedBall이 목적지에 있고 BlueBall은 다른 곳에 있다면 answer = count
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Position_13460 {
public int y_red, x_red, y_blue, x_blue;
public Position_13460(int y_red, int x_red, int y_blue, int x_blue) {
this.y_red = y_red;
this.x_red = x_red;
this.y_blue = y_blue;
this.x_blue = x_blue;
}
}
public class Problem_13460 {
static int size_n;
static int size_m;
static String[][] map;
static Queue<Position_13460> queue = new LinkedList<>();
static boolean[][][][] checked;
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, 1, 0, -1};
static int ry, rx, by, bx;
static int count = 1;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String config = br.readLine();
st = new StringTokenizer(config, " ");
size_n = Integer.parseInt(st.nextToken());
size_m = Integer.parseInt(st.nextToken());
map = new String[size_n][size_m];
checked = new boolean[10][10][10][10];
int y_red = 0;
int x_red = 0;
int y_blue = 0;
int x_blue = 0;
for(int i=0; i<size_n; ++i){
String input = br.readLine();
for(int j=0; j<size_m; ++j){
map[i][j] = input.substring(j, j+1);
if(map[i][j].equals("B")){
y_blue = i;
x_blue = j;
}
else if(map[i][j].equals("R")){
y_red = i;
x_red = j;
}
}
}
queue.offer(new Position_13460(y_red, x_red, y_blue, x_blue));
checked[y_red][x_red][y_blue][x_blue] = true;
doProcess();
System.out.println(answer);
}
private static void doProcess() {
while (!queue.isEmpty()){
int size = queue.size();
if(count > 10){
answer = -1;
return;
}
while (size > 0){
Position_13460 q = queue.poll();
int y_red = q.y_red;
int x_red = q.x_red;
int y_blue = q.y_blue;
int x_blue = q.x_blue;
for(int i=0; i<4; ++i){
ArrayList<Integer> movedPosRed = moveBall(y_red, x_red, i); //move red ball
ArrayList<Integer> movedPosBlue = moveBall(y_blue, x_blue, i); //move blue ball
ry = movedPosRed.get(0);
rx = movedPosRed.get(1);
by = movedPosBlue.get(0);
bx = movedPosBlue.get(1);
if(!map[by][bx].equals("O")){
if(map[ry][rx].equals("O")){
answer = count;
return;
}
//두개가 같은 위치에 있다면
else if(ry == by && rx == bx){
//redball이 더 많이 움직였다면 한칸 되돌리기
if(movedPosRed.get(2) > movedPosBlue.get(2)){
ry -= dy[i];
rx -= dx[i];
} else {
by -= dy[i];
bx -= dx[i];
}
}
if(!checked[ry][rx][by][bx]){
checked[ry][rx][by][bx] = true;
queue.offer(new Position_13460(ry, rx, by, bx));
}
}
}
size--;
}
count++;
}
answer = -1;
return;
}
private static ArrayList<Integer> moveBall(int y, int x, int dir) {
ArrayList<Integer> lists = new ArrayList<>();
int moveY;
int moveX;
int moveCnt = 0;
while (true){
moveY = y + dy[dir];
moveX = x + dx[dir];
moveCnt++;
if(map[moveY][moveX].equals("#") || map[y][x].equals("O")) break;
y = moveY;
x = moveX;
}
lists.add(y);
lists.add(x);
lists.add(moveCnt);
return lists;
}
}
[2048 easy _ 12100]
* 조건
1. 보드를 4개의 방향으로 기울일 때, 존재하는 블록들이 동시에 해당 방향으로 기울어져야 함
2. 블록의 값이 같다면 더해서 하나의 블록으로 변환
3. 한 사이클이 진행되는 동안 한번 병합된 블록은 더 이상 병합 불가능
4. 최대 5번까지 움직일 수 있음
* 알고리즘
- 4개 방향(상,하,좌,우)을 고려해 이동되는 모든 경우의 수를 탐색 및 최댓값 찾기: 브루트포스, 재귀
* 로직(Logic)
- 복사(깊은 복사)한 배열을 가지고 해당 방향으로 기울이고 병합한 뒤 해당 배열을 리턴
- 배열의 값이 0이 아니면 큐에 넣어주고 해당 인덱스 값은 0으로 변경
- 기울일 방향에 맞게 병합 및 배치
- 움직인 횟수(count)가 == 5 이면 answer = 최댓값으로 덮어줌
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 Problem_12100 {
static int n;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
int[][] map = new int[n][n];
for(int i=0; i<n; ++i){
String input = br.readLine();
st = new StringTokenizer(input, " ");
for(int j=0; j<n; ++j){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
//시계방향(위, 오, 아, 왼)
for(int i=0; i<4; ++i){
int count = 0;
doSolve(count, map, i);
}
System.out.println(answer);
}
private static void doSolve(int count, int[][] map, int dir) {
if(count == 5){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
answer = Math.max(answer, map[i][j]);
}
}
return;
}
int[][] tmp = moveMap(map, dir);
for(int i=0; i<4; ++i){
doSolve(count+1, tmp, i);
}
}
private static int[][] moveMap(int[][] map, int dir) {
int[][] clonedMap = new int[n][n];
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
clonedMap[i][j] = map[i][j];
}
}
int idx;
Queue<Integer> queue = new LinkedList<>();
//시계방향(위,오,아,왼)
switch (dir){
case 0:
for(int j=0; j<n; ++j){
for(int i=0; i<n; ++i){
if(clonedMap[i][j] != 0){
queue.offer(clonedMap[i][j]);
clonedMap[i][j] = 0;
}
}
idx = 0;
while (!queue.isEmpty()){
int q = queue.poll();
if(clonedMap[idx][j] == 0){
clonedMap[idx][j] = q;
}
//값이 같으면 더해주기
else if(clonedMap[idx][j] == q){
clonedMap[idx++][j] += q;
}
//다르다면 한칸 아래에다 값 넣기
else clonedMap[++idx][j] = q;
}
}
break;
case 1:
for(int i=0; i<n; ++i){
for(int j=n-1; j>=0; --j){
if(clonedMap[i][j] != 0){
queue.offer(clonedMap[i][j]);
clonedMap[i][j] = 0;
}
}
idx = n-1;
while (!queue.isEmpty()){
int q = queue.poll();
if(clonedMap[i][idx] == 0){
clonedMap[i][idx] = q;
}
//값이 같으면 더해주기
else if(clonedMap[i][idx] == q){
clonedMap[i][idx--] += q;
}
//다르다면 한칸 옆에다 값 넣기
else clonedMap[i][--idx] = q;
}
}
break;
case 2:
for(int j=0; j<n; ++j){
for(int i=n-1; i>=0; --i){
if(clonedMap[i][j] != 0){
queue.offer(clonedMap[i][j]);
clonedMap[i][j] = 0;
}
}
idx = n-1;
while (!queue.isEmpty()){
int q = queue.poll();
if(clonedMap[idx][j] == 0){
clonedMap[idx][j] = q;
}
//값이 같으면 더해주기
else if(clonedMap[idx][j] == q){
clonedMap[idx--][j] += q;
}
//다르다면 한칸 위에다 값 넣기
else clonedMap[--idx][j] = q;
}
}
break;
case 3:
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(clonedMap[i][j] != 0){
queue.offer(clonedMap[i][j]);
clonedMap[i][j] = 0;
}
}
idx = 0;
while (!queue.isEmpty()){
int q = queue.poll();
if(clonedMap[i][idx] == 0){
clonedMap[i][idx] = q;
}
//값이 같으면 더해주기
else if(clonedMap[i][idx] == q){
clonedMap[i][idx++] += q;
}
//다르다면 한칸 옆에다 값 넣기
else clonedMap[i][++idx] = q;
}
}
break;
}
return clonedMap;
}
}
여러 문제를 풀수록 여러 방법을 익혀나가게 되고, 익혀나갈수록 문제에 대한 접근을 잘 해낼 수 있다는 것을 느낀 하루였다. 지금은 반복과 습득이 답이지만 시간 안에 풀 수 있는 날이 올 거라고 믿어본다..