λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Algorithm

πŸ€” BOJ16954 μ›€μ§μ΄λŠ” 미둜 νƒˆμΆœ (Java)

πŸ“Œ 문제

색상 의미
                                                             κ΅¬ν˜„
                                                             μ£Όμ˜ν•  점
                                                             κ²°λ‘ 

μš±μ œλŠ” 학ꡐ μˆ™μ œλ‘œ 크기가 8×8인 μ²΄μŠ€νŒμ—μ„œ νƒˆμΆœν•˜λŠ” κ²Œμž„μ„ λ§Œλ“€μ—ˆλ‹€. 체슀판의 λͺ¨λ“  칸은 λΉˆ μΉΈ λ˜λŠ” λ²½ 쀑 ν•˜λ‚˜μ΄λ‹€. 욱제의 μΊλ¦­ν„°λŠ” κ°€μž₯ μ™Όμͺ½ μ•„λž« 칸에 있고, 이 μΊλ¦­ν„°λŠ” κ°€μž₯ 였λ₯Έμͺ½ μœ— 칸으둜 이동해야 ν•œλ‹€.

이 κ²Œμž„μ˜ νŠΉμ§•μ€ 벽이 μ›€μ§μΈλ‹€λŠ” 점이닀. 1μ΄ˆλ§ˆλ‹€ λͺ¨λ“  벽이 μ•„λž˜μ— μžˆλŠ” ν–‰μœΌλ‘œ ν•œ μΉΈμ”© λ‚΄λ €κ°€κ³ , κ°€μž₯ μ•„λž˜μ— μžˆμ–΄μ„œ μ•„λž˜μ— 행이 μ—†λ‹€λ©΄ 벽이 μ‚¬λΌμ§€κ²Œ λœλ‹€. 욱제의 μΊλ¦­ν„°λŠ” 1μ΄ˆμ— μΈμ ‘ν•œ ν•œ μΉΈ λ˜λŠ” λŒ€κ°μ„  λ°©ν–₯으둜 μΈμ ‘ν•œ ν•œ 칸으둜 μ΄λ™ν•˜κ±°λ‚˜, ν˜„μž¬ μœ„μΉ˜μ— μ„œ μžˆμ„ 수 μžˆλ‹€. 이동할 λ•ŒλŠ” 빈 칸으둜만 이동할 수 μžˆλ‹€.

1초 λ™μ•ˆ 욱제의 캐릭터가 λ¨Όμ € μ΄λ™ν•˜κ³ , κ·Έ λ‹€μŒ 벽이 μ΄λ™ν•œλ‹€. 벽이 캐릭터가 μžˆλŠ” 칸으둜 μ΄λ™ν•˜λ©΄ 더 이상 μΊλ¦­ν„°λŠ” 이동할 수 μ—†λ‹€.

욱제의 캐릭터가 κ°€μž₯ 였λ₯Έμͺ½ μœ— 칸으둜 이동할 수 μžˆλŠ”μ§€ μ—†λŠ”μ§€ κ΅¬ν•΄λ³΄μž.

πŸ“Œ μž…λ ₯

8개 쀄에 κ±Έμ³μ„œ 체슀판의 μƒνƒœκ°€ 주어진닀. '.'은 빈 μΉΈ, '#'λŠ” 벽이닀. κ°€μž₯ μ™Όμͺ½ μ•„λž«μΉΈμ€ 항상 벽이 μ•„λ‹ˆλ‹€.

πŸ“Œ μΆœλ ₯

욱제의 캐릭터가 κ°€μž₯ 였λ₯Έμͺ½ μœ— 칸에 도착할 수 있으면 1, μ—†μœΌλ©΄ 0을 좜λ ₯ν•œλ‹€.

πŸ“Œ 예제 μž…λ ₯

https://www.acmicpc.net/problem/16954
https://www.acmicpc.net/problem/16954
https://www.acmicpc.net/problem/16954
https://www.acmicpc.net/problem/16954
https://www.acmicpc.net/problem/16954

 

πŸ“Œ μš”μ•½

  • 체슀판의 ν¬κΈ°λŠ” 8x8둜 μ΄λ£¨μ–΄μ Έμžˆλ‹€.
  • '.' 은 빈칸, '#' 은 벽을 μ˜λ―Έν•œλ‹€.
  • 1μ΄ˆλ§ˆλ‹€ 벽은 μ•„λž˜λ‘œ λ‚΄λ €μ˜¨λ‹€.
  • μΌ€λ¦­ν„°λŠ” (μƒν•˜μ’Œμš°, λŒ€κ°μ„ , κ·ΈλŒ€λ‘œ) 이동할 수 μžˆλ‹€.
  • 움직이면 1μ΄ˆκ°€ μ†Œλͺ¨λ˜λ©°, λ‹€μŒμœΌλ‘œ 벽이 λ‚΄λ €μ˜¨λ‹€.
  • μΌ€λ¦­ν„°λŠ” μ™Όμͺ½ μ•„λž˜(7, 0)에 μœ„μΉ˜ν•˜λ©°, 였λ₯Έμͺ½ μœ„(0, 7)에 도착할 수 μžˆλŠ”μ§€ μ•Œμ•„λ‚΄μ•Ό ν•œλ‹€.

 

πŸ“Œ 풀이

  1. BFS둜 ν’€λ©΄ λ˜κ² λ‹€κ³  생각이 λ“€μ—ˆλ‹€.
  2. κ·ΈλŒ€λ‘œ κ΅¬ν˜„ν•΄λ„ λ˜κ² μ§€λ§Œ, 3차원 배열을 μ΄μš©ν•΄μ„œ nμ΄ˆμ— 벽이 λ‚΄λ €μ™”λŠ”μ§€ μƒνƒœλ₯Ό μ €μž₯ν–ˆλ‹€.
    (예λ₯Ό λ“€μžλ©΄ wall[x][y][k]λŠ” (x, y)에 kμ΄ˆμ— 벽이 λ‚΄λ €μ™”λŠ”μ§€ μƒνƒœλ₯Ό μ €μž₯ν•  수 μžˆλ‹€.)
  3. λ¨Όμ € 큐에 κ°€μž₯ μ™Όμͺ½(7, 0)에 ν˜„μž¬ μ‹œκ°„ 0초λ₯Ό λ„£λŠ”λ‹€.
  4. 큐λ₯Ό μˆœνšŒν•˜λ©΄μ„œ μ‹œκ°„μ΄ 8μ΄ˆκ°€ λ„˜μ–΄κ°€λŠ” κ²½μš°λž‘ 도착 μ§€μ κΉŒμ§€ μ™”λ‹€λ©΄ 도착할 수 μžˆλ‹€κ³  νŒλ‹¨ν•œλ‹€.
    μ™œλƒν•˜λ©΄ 8x8 체크판으둜 이루어져 있기 λ•Œλ¬Έμ— κ°€μž₯ μœ„μ— μžˆλŠ” 벽도 7초면 맨 μ•„λž˜κΉŒμ§€ 도착 ν•  수 μžˆλ‹€.
  5. 이전에 κ·ΈλŒ€λ‘œ μ›€μ§μ˜€μ„ 경우λ₯Ό μœ„ν•΄, kμ΄ˆμ— 벽이 μ‘΄μž¬ν•˜λ©΄ λ‹€λ₯Έ λ°©ν–₯을 ν™•μΈν•˜μ§€ μ•Šλ„λ‘ κ΅¬ν˜„ν–ˆλ‹€.
  6. μ΄ν›„λ‘œλŠ” (μƒν•˜μ’Œμš°, λŒ€κ°μ„ , κ·ΈλŒ€λ‘œ) μ›€μ§μ΄λ©΄μ„œ λ²”μœ„κ°€ λ„˜μ–΄κ°€λŠ”μ§€ μ²΄ν¬ν•˜κ³ , kμ΄ˆμ— 벽이 μ‘΄μž¬ν•˜λŠ”μ§€ ν™•μΈν•œλ‹€.
  7. 쑰건에 맞으면 ν˜„μž¬ μ‹œκ°„ + 1을 ν•΄μ„œ 큐에 λ„£λŠ”λ‹€.

πŸ“Œ μ½”λ“œ

import java.util.LinkedList;
import java.util.Queue;

public class BOJ16954 {

	int[] dx = {0, -1, 0, 1, 1, -1, 1, -1};
	int[] dy = {1, 0, -1, 0, 1, -1, -1, 1};

	public int solution(char[][] board) {
		int max = 8;
		boolean[][][] wall = init(board, max);
		Queue<Person> q = new LinkedList<>();
		q.offer(new Person(7, 0, 0)); //μ™Όμͺ½ μ•„λž˜μ—μ„œ 좜발

		while (!q.isEmpty()) {
			Person cur = q.poll();

			if (cur.time >= max || cur.x == 0 && cur.y == 7) return 1; //8초 μ΄μƒμ΄κ±°λ‚˜ 였λ₯Έμͺ½ μœ„λ‘œ λ„μ°©ν•˜λ©΄ κ°€λŠ₯ν•œ κ²ƒμœΌλ‘œ νŒλ‹¨
			if (wall[cur.x][cur.y][cur.time]) continue; //ν•΄λ‹Ή μ‹œκ°„μ— 벽이 μ‘΄μž¬ν•˜λ©΄ λ‹€λ₯Έ λ°©ν–₯은 ν™•μΈν•˜μ§€ μ•ŠλŠ”λ‹€.

			for (int i = 0; i < max; i++) { //μƒν•˜μ’Œμš°, λŒ€κ°μ„  확인
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= max || ny >= max) continue; //λ²”μœ„ λ²—μ–΄λ‚˜λŠ”μ§€ ν™•μΈν•˜κΈ°
				if (wall[nx][ny][cur.time]) continue; //ν•΄λ‹Ή μ‹œκ°„μ— 벽이 μ‘΄μž¬ν•˜λŠ” 확인
				q.offer(new Person(nx, ny, cur.time + 1));
			}
			q.offer(new Person(cur.x, cur.y, cur.time + 1)); //μ‹œκ°„μ„ 늘리고, 움직이지 μ•ŠλŠ” 경우 큐에 λ„£κΈ°
		}
		return 0;
	}

	private boolean[][][] init(char[][] board, int max) {
		boolean[][][] result = new boolean[max][max][max];

		for (int i = 0; i < max; i++) {
			for (int j = 0; j < max; j++) {

				if (board[i][j] == '#') { //맨 μ•„λž˜κΉŒμ§€ 벽을 μ΄λ™ν•˜μ—¬ μ‹œκ°„μ„ μ²΄ν¬ν•œλ‹€.
					int time = 0;
					for (int k = i; k < max; k++) {
						result[k][j][time++] = true;
					}
				}
			}
		}
		return result;
	}

	static class Person {
		int x, y, time; //x,y μ’Œν‘œμ™€ ν˜„μž¬ μ‹œκ°„

		public Person(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}

 

 

16954번: μ›€μ§μ΄λŠ” 미둜 νƒˆμΆœ

μš±μ œλŠ” 학ꡐ μˆ™μ œλ‘œ 크기가 8×8인 μ²΄μŠ€νŒμ—μ„œ νƒˆμΆœν•˜λŠ” κ²Œμž„μ„ λ§Œλ“€μ—ˆλ‹€. 체슀판의 λͺ¨λ“  칸은 λΉˆ μΉΈ λ˜λŠ” λ²½ 쀑 ν•˜λ‚˜μ΄λ‹€. 욱제의 μΊλ¦­ν„°λŠ” κ°€μž₯ μ™Όμͺ½ μ•„λž« 칸에 있고, 이 μΊλ¦­ν„°λŠ” κ°€μž₯ 였λ₯Έμͺ½

www.acmicpc.net