[BOJ/JAVA] 백준 13460번 : 구슬 탈출 2

13460번: 구슬 탈출 2

 

 

 

---

 

 

 

• 내용

 

스타트링크가 있다. 스타트링크의 테두리는 막혀있고, 스타트링크 안에는 빨간 구슬, 파란 구슬, 스타트링크를 빠져나갈 수 있는 구멍이 있다. 게임의 목표는 빨간 구슬을 스타트링크를 빠져나갈 수 있는 구멍이다.

 

빼내는 방법은 중력을 이용해서 빼내야한다. 상, 하, 좌, 우로 기울이면 중력에따라서 구슬이 움직이는 구조이다.

 

최소 몇번의 상, 하, 좌, 우로 기울여서 빨간 구슬을 스타트링크에서 빼낼 수 있는지 출력하면 된다. 단, 10번 이하로 움직여서 빼낼 수 없으면 -1을 출력한다.

 

 

 

• 생각

 

재귀 형식으로 네 방향을 돌려가면서 10번 이하일때 골인할 때만 answer 변수를 초기화 시켜주었다.

 

 

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Algorithm {
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };
	static int N, M, answer;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		char[][] array = new char[N][M];
		answer = Integer.MAX_VALUE;
		int bX = 0, bY = 0, rX = 0, rY = 0;
		
		String s;
		for(int i = 0; i < N; i++) {
			s = in.nextLine();
			for(int j = 0 ; j < M; j++) {
				array[i][j] = s.charAt(j);
				if(array[i][j] == 'B') {
					bX = i;
					bY = j;
				}
				if(array[i][j] == 'R') {
					rX = i;
					rY = j;
				}
			}
		}
		
		for(int i = 0; i < 4; i++) {
			bfs(array, i, 0, bX, bY, rX, rY);
		}
		
		if(answer == Integer.MAX_VALUE) answer = -1;
	}
	
	private static void bfs(char[][] array,int index, int count, int bX, int bY, int rX, int rY) {
		if(count > 9) {
			return;
		}
		int blueX = bX;
		int blueY = bY;
		int redX = rX;
		int redY = rY;
		/*
		System.out.println("\n");
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}*/
			
		
		boolean check = false, check2 = false;
		while(true) {
			// move
			blueX += x[index];
			blueY += y[index];
			redX += x[index];
			redY += y[index];
			
			// 움직일 수 없는 경우
			if((array[blueX][blueY] == '#' || (blueX + x[index] == redX && blueY + y[index] == redY)) &&
					(array[redX][redY] == '#' || (redX + x[index] == blueX && redY + y[index] == blueY))) {
				blueX -= x[index];
				blueY -= y[index];
				redX -= x[index];
				redY -= y[index];
				if(array[blueX+x[index]][blueY+y[index]] == 'O')
					check = true;
				break;
			}
			
			// 앞이 막혀있는 경우
			if(array[blueX][blueY] == '#') {
				blueX -= x[index];
				blueY -= y[index];
			}
			
			if(array[redX][redY] == '#') {
				redX -= x[index];
				redY -= y[index];
			}
			
			// 골인
			if(array[redX][redY] == 'O') {
				check2 = true; 
			}
			
			// 잘못된 골인
			if(array[blueX][blueY] == 'O') {
				check = true;
				break;				
			}
			
		}
		
		if(!check && check2) {
			answer = Math.min(answer, count+1);
			return;
		}
		
		if(!check) {
			char temp = array[blueX][blueY];
			array[blueX][blueY] = array[bX][bY];
			array[bX][bY] = temp;
			temp = array[redX][redY];
			array[redX][redY] = array[rX][rY];
			array[rX][rY] = temp;
			count++;
		} else {
			blueX = bX;
			blueY = bY;
			redX = rX;
			redY = rY;
		}
		
		for(int i = 0; i < 4; i++) {
			if(i == index) continue;
			
			bfs(array, i, count, blueX, blueY, redX, redY);
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

• 다른 사람의 더 좋은 코드

큐와 노드를 통해서 되게 깔끔하게 작성했다.. 똑똑하다...

 

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

public class Main {

	static int N, M; // N 세로, M 가로
	static int[] dirx = { -1, 0, 1, 0 };
	static int[] diry = { 0, -1, 0, 1 };
	static char map[][];

	static boolean[][][][] visit;

	static Queue<Node> queue = new LinkedList<Node>();

	public static void main(String[] args) throws Exception {

		InputStreamReader ir = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(ir);

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

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

		Node initNode = new Node(0, 0, 0, 0, 0);

		for (int n = 0; n < N; n++) {
			String token = br.readLine();
			for (int m = 0; m < M; m++) {
				char tmp = token.charAt(m);
				map[m][n] = tmp;
				if (tmp == 'R') {
					initNode.rx = m;
					initNode.ry = n;
				}
				if (tmp == 'B') {
					initNode.bx = m;
					initNode.by = n;
				}
			}
		}

		queue.offer(initNode);

		while (!queue.isEmpty()) {
			Node node = queue.poll();

			visit[node.rx][node.ry][node.bx][node.by] = true;

			if (node.count >= 10)
			{
				continue;
			}

			for (int i = 0; i < 4; i++) {
				int bx = node.bx;
				int by = node.by;
				int rx = node.rx;
				int ry = node.ry;
				// 파란색 구슬부터 굴림.
				while (map[bx + dirx[i]][by + diry[i]] != '#') {
					bx += dirx[i];
					by += diry[i];
					if (map[bx][by] == 'O')
						break;
				}

				if (map[bx][by] == 'O')
					continue;

				while (map[rx + dirx[i]][ry + diry[i]] != '#') {
					rx += dirx[i];
					ry += diry[i];
					if (map[rx][ry] == 'O')
						break;
				}

				if (map[rx][ry] == 'O') {
					System.out.println(node.count + 1);
					return;
				}

				// 겹치는 경우 처리
				if (bx == rx && by == ry) {
					switch (i) {
					case 0:
						if (node.bx > node.rx) {
							bx += 1;
						} else
							rx += 1;
						break;
					case 1:
						if (node.by > node.ry) {
							by += 1;
						} else
							ry += 1;
						break;
					case 2:
						if (node.bx > node.rx) {
							rx -= 1;
						} else
							bx -= 1;
						break;
					case 3:
						if (node.by > node.ry) {
							ry -= 1;
						} else
							by -= 1;
						break;
					}
				}

				if (!visit[rx][ry][bx][by]) {
					queue.offer(new Node(rx, ry, bx, by, node.count + 1));
				}
			}
		}
		System.out.println(-1);
	}
}

class Node {
	public int rx;
	public int ry;
	public int bx;
	public int by;
	public int count;

	public Node() {
	}

	public Node(int rx, int ry, int bx, int by, int count) {
		this.rx = rx;
		this.ry = ry;
		this.bx = bx;
		this.by = by;
		this.count = count;
	}
}