본문 바로가기
Algorithm/문제 풀이

[알고리즘] 구슬 탈출 2 (백준 13460번)

by Sky Titan 2020. 10. 2.
728x90
 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 삼성 기출 문제이다. 삼성 기출에서 자주 나오는 맵에서 물체들을 동시에 움직이는 시뮬레이션 유형이다. BFS를 활용하여서 빨간 공이 구멍에 빠지는 최단 시간을 알아내야한다.

 

Solution

 시뮬레이션 문제 중 물체를 동시에 움직이는 문제는 항상 까다롭다. 이 경우는 보드를 기울일 때 고려해야할 상황이 많다.

  1. 상하좌우로 기울일 때, 어떤 공을 먼저 움직여야 동기화가 될 지
  2. 움직이다 다른 공을 만나면 멈춰야 됨
  3. 움직이는 도중 구멍을 만나면 멈춰야 됨
  4. 빨간 공, 파란 공이 동시에 구멍에 빠질 수 있음

 

1. 전역 변수

	static int N, M;
	static boolean visited[][][][];
	static char[][] map;

 필요 전역 분수들이다. map과 빨간 공, 파란 공의 방문 여부를 체크하는 visited이다. 공들이 동시에 움직이기에 무조건  4차원 배열로 동시에 체크해야한다.

 [빨간 공 x][빨간 공 y][파란 공 x][파란 공 y]

 

2. 공들 위치 데이터 클래스

	static class Balls
	{
		int r_x, r_y, b_x, b_y, count;

		public Balls(int r_x, int r_y, int b_x, int b_y, int count) {
			this.r_x = r_x;
			this.r_y = r_y;
			this.b_x = b_x;
			this.b_y = b_y;
			this.count = count;
		}

		@Override
		public String toString() {
			return "("+r_x+", "+r_y+"), ("+b_x+", "+b_y+"), count : "+count;
		}
	}

 빨간 공, 파란 공의 위치와 이 때까지 움직인 횟수를 보관하는 데이터 홀더 클래스이다.

 

3. bfs 함수

	static int bfs(Balls start)
	{
		Queue<Balls> queue = new LinkedList<>();
		visited[start.r_x][start.r_y][start.b_x][start.b_y] = true;
		queue.offer(start);

		while(!queue.isEmpty())
		{
			Balls now = queue.poll();

			//종료
			if(now.count > 10)
				return -1;
			if(map[now.r_x][now.r_y] == 'O')
				return now.count;

			//상하좌우 기울이기
			for(int i = 0;i < 4;i++)
			{
				int next[] = tilt(now, i);
				//System.out.println(now.toString());
				if(isInBoundary(next))
				{
					//방문 x && 파란 볼이 구멍에 안빠지면
					if(!visited[next[0]][next[1]][next[2]][next[3]] && map[next[2]][next[3]] != 'O')
					{
						visited[next[0]][next[1]][next[2]][next[3]] = true;
						queue.offer(new Balls(next[0],next[1], next[2], next[3], now.count + 1));
					}
				}
			}
		}

		return -1;
	}

 맨 첫 공들의 위치를 입력받고 bfs를 돌려서 상하좌우로 공들을 기울인 뒤 방문 여부와 파란 볼이 구멍에 빠지지 않았다면 queue에 추가한다.

 빨간 공이 구멍에 빠지거나, count 횟수가 10을 넘어가면 종료한다.

 

4. boundary 체크 함수

	static boolean isInBoundary(int next[])
	{
		if(0 <= next[0] && next[0] < N && 0 <= next[1] && next[1] < M
				&& 0 <= next[2] && next[2] < N && 0 <= next[3] && next[3] < M)
			return true;
		return false;
	}

 움직인 공들의 위치가 경계 안에 있는지 체크한다.

 

5. tilt 함수

	static int[] tilt(Balls now, int dir)
	{
		int next[] = {now.r_x, now.r_y, now.b_x, now.b_y};

		//상하 좌우
		if(dir == 0)
		{
			//빨간공 먼저 기울이기
			if(now.r_x < now.b_x)
			{
				for(int i = now.r_x;i >= 0 && map[i][now.r_y] != '#'; i--)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int i = now.b_x;i >= 0 && (map[i][now.b_y] != '#' && (next[0] != i || next[1] != now.b_y)) || map[i][now.b_y] == 'O'; i--)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int i = now.b_x;i >= 0 && map[i][now.b_y] != '#'; i--)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int i = now.r_x;i >= 0 && (map[i][now.r_y] != '#' && (next[2] != i || next[3] != now.r_y)) || map[i][now.r_y] == 'O'; i--)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//하
		else if(dir == 1)
		{
			//빨간공 먼저
			if(now.r_x > now.b_x)
			{
				for(int i = now.r_x;i < N && map[i][now.r_y] != '#'; i++)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int i = now.b_x;i < N && (map[i][now.b_y] != '#' && (next[0] != i || next[1] != now.b_y)) || map[i][now.b_y] == 'O'; i++)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int i = now.b_x;i < N && map[i][now.b_y] != '#'; i++)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int i = now.r_x;i < N && (map[i][now.r_y] != '#'&& (next[2] != i || next[3] != now.r_y)) || map[i][now.r_y] == 'O'; i++)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//좌
		else if(dir == 2)
		{
			//빨간공 먼저
			if(now.r_y < now.b_y)
			{
				for(int j = now.r_y;j >= 0 && map[now.r_x][j] != '#'; j--)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int j = now.b_y;j >= 0 && (map[now.b_x][j] != '#' && (next[0] != now.b_x || next[1] != j)) || map[now.b_x][j] == 'O'; j--)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int j = now.b_y;j >= 0 && map[now.b_x][j] != '#'; j--)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int j = now.r_y;j >= 0 && (map[now.r_x][j] != '#' && (next[2] != now.r_x || next[3] != j)) || map[now.r_x][j] == 'O'; j--)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//우
		else
		{
			//빨간공 먼저
			if(now.r_y > now.b_y)
			{
				for(int j = now.r_y;j < M && map[now.r_x][j] != '#'; j++)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int j = now.b_y;j < M && (map[now.b_x][j] != '#' && (next[0] != now.b_x || next[1] != j)) || map[now.b_x][j] == 'O'; j++)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int j = now.b_y;j < M && map[now.b_x][j] != '#'; j++)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int j = now.r_y;j < M && (map[now.r_x][j] != '#' && (next[2] != now.r_x || next[3] != j)) || map[now.r_x][j] == 'O'; j++)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}

		return next;
	}

 이 문제의 가장 핵심인 보드를 상하좌우로 기울이는 함수다. 아까 말했다시피 공끼리 부딪히는 경우, 둘이 동시에 구멍에 빠지는 경우 등을 고려해야한다.

 공들을 옮길 때는 방향에따라 해당 방향으로 앞서있는 공을 먼저 움직여야 동시에 움직인 것과 같은 효과가 난다. 예를 들어 위쪽으로 기울이면 빨간 공과 파란 공 중 더 위쪽에 있는 공을 움직여야 된다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int N, M;
	static boolean visited[][][][];
	static char[][] map;

	public static void solution() throws Exception
	{
		String[] list = br.readLine().split(" ");
		N = Integer.parseInt(list[0]);
		M = Integer.parseInt(list[1]);

		map = new char[N][M];
		visited = new boolean[N][M][N][M];

		Balls start = new Balls(0,0,0,0,0);

		for(int i = 0;i < N;i++)
		{
			String line = br.readLine();
			for(int j = 0;j < M;j++)
			{
				map[i][j] = line.charAt(j);

				if(map[i][j] == 'R')
				{
					start.r_x = i;
					start.r_y = j;
					map[i][j] = '.';
				}
				else if(map[i][j] == 'B')
				{
					start.b_x = i;
					start.b_y = j;
					map[i][j] = '.';
				}
			}
		}

		bw.write(bfs(start)+"");
	}

	static int bfs(Balls start)
	{
		Queue<Balls> queue = new LinkedList<>();
		visited[start.r_x][start.r_y][start.b_x][start.b_y] = true;
		queue.offer(start);

		while(!queue.isEmpty())
		{
			Balls now = queue.poll();

			//종료
			if(now.count > 10)
				return -1;
			if(map[now.r_x][now.r_y] == 'O')
				return now.count;

			//상하좌우 기울이기
			for(int i = 0;i < 4;i++)
			{
				int next[] = tilt(now, i);
				//System.out.println(now.toString());
				if(isInBoundary(next))
				{
					//방문 x && 파란 볼이 구멍에 안빠지면
					if(!visited[next[0]][next[1]][next[2]][next[3]] && map[next[2]][next[3]] != 'O')
					{
						visited[next[0]][next[1]][next[2]][next[3]] = true;
						queue.offer(new Balls(next[0],next[1], next[2], next[3], now.count + 1));
					}
				}
			}
		}

		return -1;
	}

	static boolean isInBoundary(int next[])
	{
		if(0 <= next[0] && next[0] < N && 0 <= next[1] && next[1] < M
				&& 0 <= next[2] && next[2] < N && 0 <= next[3] && next[3] < M)
			return true;
		return false;
	}

	static int[] tilt(Balls now, int dir)
	{
		int next[] = {now.r_x, now.r_y, now.b_x, now.b_y};

		//상하 좌우
		if(dir == 0)
		{
			//빨간공 먼저 기울이기
			if(now.r_x < now.b_x)
			{
				for(int i = now.r_x;i >= 0 && map[i][now.r_y] != '#'; i--)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int i = now.b_x;i >= 0 && (map[i][now.b_y] != '#' && (next[0] != i || next[1] != now.b_y)) || map[i][now.b_y] == 'O'; i--)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int i = now.b_x;i >= 0 && map[i][now.b_y] != '#'; i--)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int i = now.r_x;i >= 0 && (map[i][now.r_y] != '#' && (next[2] != i || next[3] != now.r_y)) || map[i][now.r_y] == 'O'; i--)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//하
		else if(dir == 1)
		{
			//빨간공 먼저
			if(now.r_x > now.b_x)
			{
				for(int i = now.r_x;i < N && map[i][now.r_y] != '#'; i++)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int i = now.b_x;i < N && (map[i][now.b_y] != '#' && (next[0] != i || next[1] != now.b_y)) || map[i][now.b_y] == 'O'; i++)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int i = now.b_x;i < N && map[i][now.b_y] != '#'; i++)
				{
					next[2] = i;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int i = now.r_x;i < N && (map[i][now.r_y] != '#'&& (next[2] != i || next[3] != now.r_y)) || map[i][now.r_y] == 'O'; i++)
				{
					next[0] = i;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//좌
		else if(dir == 2)
		{
			//빨간공 먼저
			if(now.r_y < now.b_y)
			{
				for(int j = now.r_y;j >= 0 && map[now.r_x][j] != '#'; j--)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int j = now.b_y;j >= 0 && (map[now.b_x][j] != '#' && (next[0] != now.b_x || next[1] != j)) || map[now.b_x][j] == 'O'; j--)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int j = now.b_y;j >= 0 && map[now.b_x][j] != '#'; j--)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int j = now.r_y;j >= 0 && (map[now.r_x][j] != '#' && (next[2] != now.r_x || next[3] != j)) || map[now.r_x][j] == 'O'; j--)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}
		//우
		else
		{
			//빨간공 먼저
			if(now.r_y > now.b_y)
			{
				for(int j = now.r_y;j < M && map[now.r_x][j] != '#'; j++)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}

				for(int j = now.b_y;j < M && (map[now.b_x][j] != '#' && (next[0] != now.b_x || next[1] != j)) || map[now.b_x][j] == 'O'; j++)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}
			}
			else
			{
				for(int j = now.b_y;j < M && map[now.b_x][j] != '#'; j++)
				{
					next[3] = j;
					if(map[next[2]][next[3]] == 'O')
						break;
				}

				for(int j = now.r_y;j < M && (map[now.r_x][j] != '#' && (next[2] != now.r_x || next[3] != j)) || map[now.r_x][j] == 'O'; j++)
				{
					next[1] = j;
					if(map[next[0]][next[1]] == 'O')
						break;
				}
			}
		}

		return next;
	}


	static class Balls
	{
		int r_x, r_y, b_x, b_y, count;

		public Balls(int r_x, int r_y, int b_x, int b_y, int count) {
			this.r_x = r_x;
			this.r_y = r_y;
			this.b_x = b_x;
			this.b_y = b_y;
			this.count = count;
		}

		@Override
		public String toString() {
			return "("+r_x+", "+r_y+"), ("+b_x+", "+b_y+"), count : "+count;
		}
	}



	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}
728x90
저작자표시 비영리

'Algorithm > 문제 풀이' 카테고리의 다른 글

[알고리즘] 퍼즐 (백준 1525번)  (0) 2020.10.03
[알고리즘] 최소비용 구하기 (백준 1916번)  (0) 2020.10.02
[알고리즘] 줄 세우기 (백준 2252번)  (0) 2020.09.28
[알고리즘] 집합 (백준 11723번)  (0) 2020.09.28
[알고리즘] 캐슬 디펜스 (백준 17135번)  (0) 2020.09.28

관련글

댓글

티스토리툴바