13459: 구슬 탈출
- 간만에 풀어보는 bfs 구현 문제
- 구슬을 기울여서 움직이는 부분이 신선했다 (네이버 코테 2차에서 이와 비슷한 식으로 구현하는 문제가 있었음)
move(x, y, dx, dy)
- "board[x+dx]y+dy} != '#' and board[x][y] != 'O'"을 실행 조건으로 갖는 while문을 돌면서 구슬이 쭉 이동함
- 굴러간 거리는 1초당 1칸이라고 보고, 굴러간 거리가 작은 색깔의 구슬이 해당 자리에 있는 게 맞기 때문에 cnt (굴러간 거리)도 같이 구해서 반환해줘야함
참고 사항
- visit 처리를 해줄 때, 처음엔 board의 모양으로 False를 담아서 visit_red, visit_blue를 따로 처리해줬는데, 빨간 구슬과 파란 구슬은 함께 움직이기 때문에 이렇게 해주면 안됨
- 그냥 visit 리스트에 tuple 형태로 빨간 구슬의 위치와 파란 구슬의 위치를 한번에 넣어주는 형식으로 방문한 노드를 체크해줌
import sys
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def move(x, y, dx, dy):
cnt = 0
while board[x+dx][y+dy] != '#' and board[x][y] != 'O': #보드를 기울여서 움직여야함
x += dx; y += dy; cnt += 1
return x, y, cnt
def bfs(rx, ry, bx, by, depth):
queue = deque([])
queue.append([rx, ry, bx, by, depth]); visit.append((rx, ry, bx, by))
while queue:
rx, ry, bx, by, depth = queue.popleft()
if depth > 10:
break
for i in range(4):
nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
print(1)
return
if nrx == nbx and nry == nby: #cnt가 작은 색깔의 구슬이 해당 자리에 있는 게 맞음
if rcnt > bcnt:
nrx -= dx[i]; nry -= dy[i]
else:
nbx -= dx[i]; nby -= dy[i]
if (nrx, nry, nbx, nby) not in visit:
queue.append([nrx, nry, nbx, nby, depth+1])
visit.append((nrx, nry, nbx, nby))
print(0)
N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
board.append(list(sys.stdin.readline()[:-1]))
for m in range(M):
if board[n][m] == 'R':
rx, ry = n, m
elif board[n][m] == 'B':
bx, by = n, m
visit = []
bfs(rx, ry, bx, by, 1)13460: 구슬 탈출 2
- 그냥 "13459: 구슬 탈출" 문제에서 print(0)대신 print(-1), print(1) 대신 print(depth)를 해주면 됨
import sys
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def move(x, y, dx, dy):
cnt = 0
while board[x+dx][y+dy] != '#' and board[x][y] != 'O': #보드를 기울여서 움직여야함
x += dx; y += dy; cnt += 1
return x, y, cnt
def bfs(rx, ry, bx, by, depth):
queue = deque([])
queue.append([rx, ry, bx, by, depth]); visit.append((rx, ry, bx, by))
while queue:
rx, ry, bx, by, depth = queue.popleft()
if depth > 10:
break
for i in range(4):
nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
print(depth)
return
if nrx == nbx and nry == nby: #cnt가 작은 색깔의 구슬이 해당 자리에 있는 게 맞음
if rcnt > bcnt:
nrx -= dx[i]; nry -= dy[i]
else:
nbx -= dx[i]; nby -= dy[i]
if (nrx, nry, nbx, nby) not in visit:
queue.append([nrx, nry, nbx, nby, depth+1])
visit.append((nrx, nry, nbx, nby))
print(-1)
N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
board.append(list(sys.stdin.readline()[:-1]))
for m in range(M):
if board[n][m] == 'R':
rx, ry = n, m
elif board[n][m] == 'B':
bx, by = n, m
visit = []
bfs(rx, ry, bx, by, 1)15644: 구슬 탈출 3
- 이 문제는 depth를 출력하는 동시에, 기울인 방향을 순서대로 출력해줘야한다
- queue에 넣어주는 list에 direction 원소를 추가해줌. direction은 string 변수이며 초기값은 ''임
- 1) 기울이는 방향에 따라 ndirection의 값을 미리 할당해둠
- 2) 만약 방문하지 않은 노드라면 queue에 direction + ndirection 값을 넣어줌
- queue의 노드들은 bfs 순회를 할 때 독립적으로 존재함 -> 구슬 탈출 3번 문제와 같이 순회 경로를 기록하고자 한다면 queue의 노드에 direction을 넣어줘야함
import sys
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def move(x, y, dx, dy):
cnt = 0
while board[x+dx][y+dy] != '#' and board[x][y] != 'O': #보드를 기울여서 움직여야함
x += dx; y += dy; cnt += 1
return x, y, cnt
def bfs(rx, ry, bx, by, depth):
queue = deque([])
queue.append([rx, ry, bx, by, depth, '']); visit.append((rx, ry, bx, by))
while queue:
rx, ry, bx, by, depth, direction = queue.popleft()
if depth > 10:
break
for i in range(4):
nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
if i == 0: ndirection = 'L'
elif i == 1: ndirection = 'R'
elif i == 2: ndirection = 'U'
else: ndirection = 'D'
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
print(depth)
print(direction + ndirection)
return
if nrx == nbx and nry == nby: #cnt가 작은 색깔의 구슬이 해당 자리에 있는 게 맞음
if rcnt > bcnt:
nrx -= dx[i]; nry -= dy[i]
else:
nbx -= dx[i]; nby -= dy[i]
if (nrx, nry, nbx, nby) not in visit:
# if i == 0: direction += 'L'
# elif i == 1: direction += 'R'
# elif i == 2: direction += 'U'
# else: direction += 'D'
queue.append([nrx, nry, nbx, nby, depth+1, direction + ndirection])
visit.append((nrx, nry, nbx, nby))
print(-1)
N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
board.append(list(sys.stdin.readline()[:-1]))
for m in range(M):
if board[n][m] == 'R':
rx, ry = n, m
elif board[n][m] == 'B':
bx, by = n, m
visit = []
bfs(rx, ry, bx, by, 1)15653: 구슬 탈출 4
- if depth > 10: break 부분 없애주면 됨
import sys
from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def move(x, y, dx, dy):
cnt = 0
while board[x+dx][y+dy] != '#' and board[x][y] != 'O': #보드를 기울여서 움직여야함
x += dx; y += dy; cnt += 1
return x, y, cnt
def bfs(rx, ry, bx, by, depth):
queue = deque([])
queue.append([rx, ry, bx, by, depth]); visit.append((rx, ry, bx, by))
while queue:
rx, ry, bx, by, depth = queue.popleft()
for i in range(4):
nrx, nry, rcnt = move(rx, ry, dx[i], dy[i])
nbx, nby, bcnt = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != 'O':
if board[nrx][nry] == 'O':
print(depth)
return
if nrx == nbx and nry == nby: #cnt가 작은 색깔의 구슬이 해당 자리에 있는 게 맞음
if rcnt > bcnt:
nrx -= dx[i]; nry -= dy[i]
else:
nbx -= dx[i]; nby -= dy[i]
if (nrx, nry, nbx, nby) not in visit:
queue.append([nrx, nry, nbx, nby, depth+1])
visit.append((nrx, nry, nbx, nby))
print(-1)
N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
board.append(list(sys.stdin.readline()[:-1]))
for m in range(M):
if board[n][m] == 'R':
rx, ry = n, m
elif board[n][m] == 'B':
bx, by = n, m
visit = []
bfs(rx, ry, bx, by, 1)
Software Engineer @ LG Electronics