13459: 구슬 탈출 && 13460: 구슬 탈출 2 && 15644: 구슬 탈출 3 && 15653: 구슬 탈출 4

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)