๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

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