๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[BAEKJOON python] 13460_๊ตฌ์ฌ ํ์ถ2 ๋ณธ๋ฌธ
728x90
๋ฐ์ํ
๊ตฌ์ฌ ํ์ถ์ ์ง์ฌ๊ฐํ ๋ณด๋์ ๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํ๋์ฉ ๋ฃ์ ๋ค์,
๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด ๋นผ๋ด๋ ๊ฒ์์ด๋ค.
๋ณด๋์ ์ธ๋ก ํฌ๊ธฐ๋ N, ๊ฐ๋ก ํฌ๊ธฐ๋ M์ด๊ณ , ํธ์์ 1×1ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค.
๊ฐ์ฅ ๋ฐ๊นฅ ํ๊ณผ ์ด์ ๋ชจ๋ ๋งํ์ ธ ์๊ณ , ๋ณด๋์๋ ๊ตฌ๋ฉ์ด ํ๋ ์๋ค.
๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํฌ๊ธฐ๋ ๋ณด๋์์ 1×1ํฌ๊ธฐ์ ์นธ์ ๊ฐ๋ ์ฑ์ฐ๋ ์ฌ์ด์ฆ์ด๊ณ ๊ฐ๊ฐ ํ๋์ฉ ๋ค์ด๊ฐ ์๋ค.
๊ฒ์์ ๋ชฉํ๋ ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด์ ๋นผ๋ด๋ ๊ฒ์ด๋ค.
์ด๋, ํ๋ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ์ ๋ค์ด๊ฐ๋ฉด ์ ๋๋ค.
์ด๋, ๊ตฌ์ฌ์ ์์ผ๋ก ๊ฑด๋๋ฆด ์๋ ์๊ณ , ์ค๋ ฅ์ ์ด์ฉํด์ ์ด๋ฆฌ ์ ๋ฆฌ ๊ตด๋ ค์ผ ํ๋ค.
์ผ์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์ค๋ฅธ์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์๋์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ์ ๊ฐ์ ๋ค ๊ฐ์ง ๋์
๊ฐ๊ฐ์ ๋์์์ ๊ณต์ ๋์์ ์์ง์ธ๋ค.
๋นจ๊ฐ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ์ ๋น ์ง๋ฉด ์ฑ๊ณต์ด์ง๋ง, ํ๋ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ์ ๋น ์ง๋ฉด ์คํจ
๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ด ๋์์ ๊ตฌ๋ฉ์ ๋น ์ ธ๋ ์คํจ์ด๋ค.
๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ๋์์ ๊ฐ์ ์นธ์ ์์ ์ ์๋ค.
๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํฌ๊ธฐ๋ ํ ์นธ์ ๋ชจ๋ ์ฐจ์งํ๋ค.
๊ธฐ์ธ์ด๋ ๋์์ ๊ทธ๋งํ๋ ๊ฒ์ ๋ ์ด์ ๊ตฌ์ฌ์ด ์์ง์ด์ง ์์ ๋ ๊น์ง์ด๋ค.
๋ณด๋์ ์ํ๊ฐ ์ฃผ์ด์ก์ ๋, ์ต์ ๋ช ๋ฒ ๋ง์ ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด ๋นผ๋ผ ์ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ ์์ฑ
์ฒซ ๋ฒ์งธ ์ค์๋ ๋ณด๋์ ์ธ๋ก, ๊ฐ๋ก ํฌ๊ธฐ๋ฅผ ์๋ฏธํ๋ ๋ ์ ์ N, M (3 ≤ N, M ≤ 10)
๋ค์ N๊ฐ์ ์ค์ ๋ณด๋์ ๋ชจ์์ ๋ํ๋ด๋ ๊ธธ์ด M์ ๋ฌธ์์ด
๋ฌธ์์ด์ '.', '#', 'O', 'R', 'B' ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
'.'์ ๋น ์นธ์ ์๋ฏธํ๊ณ , '#'์ ๊ณต์ด ์ด๋ํ ์ ์๋ ์ฅ์ ๋ฌผ ๋๋ ๋ฒฝ์ ์๋ฏธํ๋ฉฐ,
'O'๋ ๊ตฌ๋ฉ์ ์์น๋ฅผ ์๋ฏธํ๋ค.
'R'์ ๋นจ๊ฐ ๊ตฌ์ฌ์ ์์น, 'B'๋ ํ๋ ๊ตฌ์ฌ์ ์์น
์ ๋ ฅ๋๋ ๋ชจ๋ ๋ณด๋์ ๊ฐ์ฅ์๋ฆฌ์๋ ๋ชจ๋ '#'์ด ์๋ค.
๊ตฌ๋ฉ์ ๊ฐ์๋ ํ ๊ฐ ์ด๋ฉฐ, ๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํญ์ 1๊ฐ๊ฐ ์ฃผ์ด์ง๋ค.
์ต์ ๋ช ๋ฒ ๋ง์ ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด ๋นผ๋ผ ์ ์๋์ง ์ถ๋ ฅ
๋ง์ฝ, 10๋ฒ ์ดํ๋ก ์์ง์ฌ์ ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด ๋นผ๋ผ ์ ์์ผ๋ฉด -1์ ์ถ๋ ฅ
# 1) BFS
import sys
from collections import deque
input = sys.stdin.readline
# ๋ณด๋์ ์ธ๋ก, ๊ฐ๋ก ํฌ๊ธฐ
N, M = map(int, input().split())
# '.'์ ๋น ์นธ
# '#'์ ๊ณต์ด ์ด๋ํ ์ ์๋ ์ฅ์ ๋ฌผ ๋๋ ๋ฒฝ
# 'O'๋ ๊ตฌ๋ฉ์ ์์น
# 'R'์ ๋นจ๊ฐ ๊ตฌ์ฌ์ ์์น
# 'B'๋ ํ๋ ๊ตฌ์ฌ์ ์์น
graph = []
for i in range(N) :
graph.append(list(input()))
for j in range(M) :
if graph[i][j] == "R" :
rx, ry = i, j
elif graph[i][j] == "B" :
bx, by = i, j
# ๊ธฐ์ธ๊ธฐ
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(rx, ry, bx, by) :
q = deque()
q.append((rx, ry, bx, by))
cnt = 0
visited = []
visited.append((rx, ry, bx, by))
while q :
for _ in range(len(q)):
rx, ry, bx, by = q.popleft()
# ์์ง์ธ๊ฑฐ 10๋ฒ ์ด์
if cnt > 10 :
print(-1)
return
# ๋นจ๊ฐ ๊ตฌ์ฌ ์์น๊ฐ ๊ตฌ๋ฉ
if graph[rx][ry] == "O" :
print(cnt)
return
# ๋ฐฉํฅ ํ์
for i in range(4) :
# ๋นจ๊ฐ ๊ตฌ์ฌ๋ถํฐ
rnx, rny = rx, ry
while True :
rnx += dx[i]
rny += dy[i]
if graph[rnx][rny] == "#" :
rnx -= dx[i]
rny -= dy[i]
break
if graph[rnx][rny] == "O" :
break
# ํ๋ ๊ตฌ์ฌ
bnx, bny = bx, by
while True :
bnx += dx[i]
bny += dy[i]
if graph[bnx][bny] == "#":
bnx -= dx[i]
bny -= dy[i]
break
if graph[bnx][bny] == "O":
break
# ํ๋ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ ๋ค์ด๊ฐ๋ฉด ์๋จ
if graph[bnx][bny] == "O" :
continue
# ๊ฐ์ด ์์ ์ ์์
if rnx == bnx and bny == rny :
if abs(rnx - rx) + abs(rny - ry) > abs(bnx - bx) + abs(bny - by) :
# ๋ ๋ง์ด ๊ฐ ์ ๊ฐ ๋ฆ๊ฒ ๊ฐ ์ ์. ๋ค๋ก ๊ฐ์
rnx -= dx[i]
rny -= dy[i]
else :
bnx -= dx[i]
bny -= dy[i]
if (rnx, rny, bnx, bny) not in visited :
q.append((rnx, rny, bnx, bny))
visited.append((rnx, rny, bnx, bny))
cnt += 1
print(-1)
bfs(rx, ry, bx, by)
# input
# 10 10
# ##########
# #R#...##B#
# #...#.##.#
# #####.##.#
# #......#.#
# #.######.#
# #.#....#.#
# #.#.#.#..#
# #...#.O#.#
# ##########
# output
# -1
728x90
๋ฐ์ํ
'๐ฆฅ ์ฝํ > BAEKJOON' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BAEKJOON python] 3190_๋ฑ (0) | 2022.10.10 |
---|---|
[BAEKJOON python] 12100_2048(easy) (0) | 2022.10.10 |
[BAEKJOON python] 14889_์คํํธ์ ๋งํฌ (0) | 2022.10.10 |
[BAEKJOON python] 14888_์ฐ์ฐ์ ๋ผ์๋ฃ๊ธฐ (0) | 2022.10.09 |
[BAEKJOON python] 14501_ํด์ฌ (0) | 2022.10.09 |
Comments