๋ฆฌ์ฝ์ณ ๋ก๋ด์ด๋ผ๋ ๋ณด๋๊ฒ์์ด ์์ต๋๋ค.
์ด ๋ณด๋๊ฒ์์ ๊ฒฉ์๋ชจ์ ๊ฒ์ํ ์์์ ๋ง์ ์์ง์ด๋ ๊ฒ์์ผ๋ก, ์์ ์์น์์ ๋ชฉํ ์์น๊น์ง ์ต์ ๋ช ๋ฒ๋ง์ ๋๋ฌํ ์ ์๋์ง ๋งํ๋ ๊ฒ์์ ๋๋ค.
์ด ๊ฒ์์์ ๋ง์ ์์ง์์ ์, ํ, ์ข, ์ฐ 4๋ฐฉํฅ ์ค ํ๋๋ฅผ ์ ํํด์ ๊ฒ์ํ ์์ ์ฅ์ ๋ฌผ์ด๋ ๋งจ ๋์ ๋ถ๋ชํ ๋๊น์ง ๋ฏธ๋๋ฌ์ ธ ์ด๋ํ๋ ๊ฒ์ ํ ๋ฒ์ ์ด๋์ผ๋ก ์นฉ๋๋ค.
๋ค์์ ๋ณด๋๊ฒ์ํ์ ๋ํ๋ธ ์์์ ๋๋ค.
...D..R
.D.G...
....D.D
D....D.
..D....
์ฌ๊ธฐ์ .
์ ๋น ๊ณต๊ฐ์, R
์ ๋ก๋ด์ ์ฒ์ ์์น๋ฅผ, D
๋ ์ฅ์ ๋ฌผ์ ์์น๋ฅผ, G
๋ ๋ชฉํ์ง์ ์ ๋ํ๋
๋๋ค.
์ ์์์์๋ R
์์น์์ ์๋, ์ผ์ชฝ, ์, ์ผ์ชฝ, ์๋, ์ค๋ฅธ์ชฝ, ์ ์์๋ก ์์ง์ด๋ฉด 7๋ฒ ๋ง์ G
์์น์ ๋ฉ์ถฐ ์ค ์ ์์ผ๋ฉฐ, ์ด๊ฒ์ด ์ต์ ์์ง์ ์ค ํ๋์
๋๋ค.
๊ฒ์ํ์ ์ํ๋ฅผ ๋ํ๋ด๋ ๋ฌธ์์ด ๋ฐฐ์ด board
๊ฐ ์ฃผ์ด์ก์ ๋, ๋ง์ด ๋ชฉํ์์น์ ๋๋ฌํ๋๋ฐ ์ต์ ๋ช ๋ฒ ์ด๋ํด์ผ ํ๋์ง return ํ๋ solution
ํจ์๋ฅผ ์์ฑํ์ธ์. ๋ง์ฝ ๋ชฉํ์์น์ ๋๋ฌํ ์ ์๋ค๋ฉด -1
์ return ํด์ฃผ์ธ์.
board
์ ๊ธธ์ด โค 100board
์ ์์์ ๊ธธ์ด โค 100board
์ ์์์ ๊ธธ์ด๋ ๋ชจ๋ ๋์ผํฉ๋๋ค.".", "D", "R", "G"
๋ก๋ง ๊ตฌ์ฑ๋์ด ์์ผ๋ฉฐ ๊ฐ๊ฐ ๋น ๊ณต๊ฐ, ์ฅ์ ๋ฌผ, ๋ก๋ด์ ์ฒ์ ์์น, ๋ชฉํ ์ง์ ์ ๋ํ๋
๋๋ค."R"
๊ณผ "G"
๋ ํ ๋ฒ์ฉ ๋ฑ์ฅํฉ๋๋ค.board | result |
---|---|
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] | 7 |
[".D.R", "....", ".G..", "...D"] | -1 |
.D.R
....
.G..
...D
"R"
์์น์ ์๋ ๋ง์ ์ด๋ป๊ฒ ์์ง์ฌ๋ "G"
์ ๋๋ฌ์ํฌ ์ ์์ต๋๋ค.-1
์ return ํฉ๋๋ค.์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ์์ผ ํ๋ ๋ฌธ์ ์ด๊ธฐ ๋๋ฌธ์, BFS๋ฅผ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์๋ค.
์ํ์ข์ฐ๋ฅผ ์ดํผ๊ธฐ ์ํด ์ด์ ๋ฌธ์ ๋ค์์ ๊ตฌํํ๋ ๊ฒ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก 2์ฐจ์ ๋ฐฐ์ด์ ์ด๋ ์ ๋ณด๋ฅผ ์ ์ฅํด ์ฌ์ฉํ์๋ค.
์ด ๋ฌธ์ ์์ ์ค์ํ ์ ์ ์ด๋ ์ค ์ฅ์ ๋ฌผ์ ๋ง๋ฌ์ ๋์ ์กฐ๊ฑด์ ์ ์ค์ ํด ์ฃผ์ด์ผ ํ๋ค๋ ๊ฒ์ด๋ค.
import java.util.*;
public class Programmers_169199 {
static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // ์ํ์ข์ฐ
static char[][] map; // ๊ฒ์ํ
static boolean[][] visited; // ๋ฐฉ๋ฌธ ์ฌ๋ถ
static int[] start = new int[2]; // ์์์ ์ขํ ์ ๋ณด
public static int solution(String[] board) {
map = new char[board.length][board[0].length()];
visited = new boolean[board.length][board[0].length()];
Queue<int[]> queue = new LinkedList<>(); // bfs๋ฅผ ๊ตฌํํ ํ ์์ฑ
// ๊ฒ์ํ ์ ์ฅ
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length(); j++) {
map[i][j] = board[i].charAt(j);
// ์์์ ์ ์ฅ
if (map[i][j] == 'R') {
start[0] = i;
start[1] = j;
}
}
}
queue.offer(start); // ์์์ ์
๋ ฅ
visited[start[0]][start[1]] = true; // ์์์ ๋ฐฉ๋ฌธ ์ฌ๋ถ ํ์
int count = 0; // ์ด๋ ํ์
while(!queue.isEmpty()) {
count++;
int size = queue.size();
for (int i = 0; i < size; i++) {
// ํ์ฌ ์์น
int[] current = queue.poll();
for (int j = 0; j < 4; j++) {
// ํ์ฌ ์ขํ
int curX = current[0];
int curY = current[1];
// ํด๋น ๋ฐฉํฅ์ผ๋ก ์งํ
while (curX + direction[j][0] >= 0 && curX + direction[j][0] < board.length &&
curY + direction[j][1] >= 0 && curY + direction[j][1] < board[0].length() &&
map[curX + direction[j][0]][curY + direction[j][1]] != 'D') {
curX = curX + direction[j][0]; // X์ขํ ์ด๋
curY = curY + direction[j][1]; // Y์ขํ ์ด๋
}
// ๋ชฉ์ ์ง์ ๋์ฐฉํ ๊ฒฝ์ฐ count ๋ฆฌํด
if (map[curX][curY] == 'G') {
return count;
}
// ์ฅ์ ๋ฌผ์ ๋งํ ๊ฒฝ์ฐ
if (!visited[curX][curY]) {
queue.add(new int[] {curX, curY});
visited[curX][curY] = true;
}
}
}
}
return -1;
}
}
๊ฒ์ํ ์ ๋ณด๋ฅผ 2์ฐจ์ ๋ฐฐ์ด map
์ ์ ์ฅํ๊ณ , ์์์ ์ขํ๋ฅผ start
๋ฐฐ์ด์ ์ ์ฅํ๋ค.
์์์ ์ขํ๋ฅผ ํ์ ๋ฃ์ด์ฃผ๊ณ , ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ ์ฅํ๋ visited
๋ฐฐ์ด์ ์์์ ์ขํ์ ๋ฐฉ๋ฌธ ์ฌ๋ถ๋ฅผ ์ ์ฅํด ์ค๋ค.
์ด๋ ํ์๋ฅผ 1์ฆ๊ฐ ์ํค๊ณ , ํ์ฌ ์ขํ์์ ์ํ์ข์ฐ๋ฅผ ์ดํด๋ณด์์ ๋, ์ด๋ํ ์ขํ๊ฐ ๊ฒ์ํ ๋ฒ์ ์์ ์๊ณ , ์ฅ์ ๋ฌผ์ด ์๋ ์์น๊ฐ ์๋ ์กฐ๊ฑด ๋ด์์ ํ์ฌ ์ขํ๋ฅผ ์ด๋์ํจ๋ค.
๋ชฉ์ ์ง์ ๋์ฐฉํ ๊ฒฝ์ฐ์๋ ๋ ์ด์ ์งํํ ํ์๊ฐ ์๊ธฐ ๋๋ฌธ์ count
๋ฅผ ๋ฐ๋ก ๋ฆฌํดํด์ค๋ค.
์ฅ์ ๋ฌผ์ ๋งํ ๊ฒฝ์ฐ์๋ ํ์ ํ์ฌ ์ขํ๋ฅผ ์ ์ฅํ๊ณ , 3~4๋ฒ ๊ณผ์ ์ ๋ค์ ๊ฑฐ์น๋ฉฐ ์ด๋์ ๊ณ์ ์งํํ๋ค.
โ๏ธ์ด๋ ๊ฒ ๋จธ๋ฆฌ ์ํ ๋ณด๋๊ฒ์์ด๋ผ๋๐ค