[BAEKJOON] 13460번. 구슬 탈출 2

 

 

---

'''
조건:
1. 빨간 구슬과 파란 구슬은 동시에 같은 자리에 있을 수 없음
2. 빨간 구슬이 구멍에 => 성공 / 파란 구슬이 구멍에 => 실패
3. 최대 10번까지 기울일 수 있음 (그 이상은 -1 출력)
4. N: 보드의 세로 크기(행), M: 보드의 가로 크기(열)
5. '.': 빈칸, '#': 벽, 'R': 빨간 구슬, 'B': 파란 구슬, 'O': 구멍
'''
def move(x, y, dx, dy):
    count = 0       # 구슬이 몇 칸 움직였나?
    # 다음 위치가 벽이 아니고 + 현재 위치가 구멍이 아닌 경우에만
    while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    return x, y, count

def dfs(rx, ry, bx, by, depth):     # depth: 기울임 횟수
    global answer
    
    # 기울임 횟수가 10을 초과하거나 최솟값보다 크면 X
    if depth > 10 or depth >= answer:
        return
    
    for i in range(4):      # 상하좌우 네 방향
        nrx, nry, r_count = move(rx, ry, dx[i], dy[i])
        nbx, nby, b_count = move(bx, by, dx[i], dy[i])

        # 파란 구슬이 구멍에 있으면 실패
        if board[nbx][nby] == 'O':
            continue
        # 빨간 구슬이 구멍에 있으면 성공
        if board[nrx][nry] == 'O':
            if answer > depth:
                answer = depth
            return
        # 파란 구슬 위치 = 빨간 구슬 위치
        # => 더 먼저 온 구슬에게 양보 (더 많이 이동한 구슬 위치 한 칸씩 빼주기)
        if (nrx == nbx) and (nry == nby):
            if r_count > b_count:   # 빨간 구슬이 더 많이 이동
                nrx -= dx[i]
                nry -= dy[i]
            else:                   # 파란 구슬이 더 많이 이동
                nbx -= dx[i]
                nby -= dy[i]
        
        # 방문하지 않은 좌표라면
        if (nrx, nry, nbx, nby) not in visited:
            visited.append((nrx, nry, nbx, nby))
            dfs(nrx, nry, nbx, nby, depth+1)
            visited.pop()

N, M = map(int, input().split())
board = [list(map(str, input().strip())) for _ in range(N)]
dx = [-1, 0, 1, 0]      # ↑, ←, ↓, →
dy = [0, -1, 0, 1]      # ↑, ←, ↓, →

# 빨간 구슬, 파란 구슬 위치 찾기
for i in range(N):
    for j in range(M):
        if board[i][j] == 'R':      # 빨간 구슬
            rx, ry = i, j
        elif board[i][j] == 'B':    # 파란 구슬
            bx, by = i, j

visited = []            # 방문 좌표 기록용
answer = float('inf')   # 최소 기울임 횟수

dfs(rx, ry, bx, by, 1)

answer = answer if answer != float('inf') else -1
print(answer)

다들 bfs로 풀었는데 난 bfs 너무 어려워서 그냥 dfs로 풀었다.

set() 자료형도 익숙치 않아서 visited = []로 했는데, set은 검색/삽입이 O(1)이라 더 효율적이라고 한다.
리스트에서 set으로 바꿔서 제출해봤는데 시간 4ms 단축돼서 지금 당장 이 문제에서는 별 차이가 없는 것 같기도.

 

+) 아기 상어 문제에서 BFS 공부한 김에 DFS 코드를 직접 BFS로 바꿔봤다.

## BFS 코드 ##

from collections import deque

def move(x, y, dx, dy):
    count = 0
    # 다음 좌표가 벽이 아니고, 현재 위치가 구멍이 아님
    while area[x+dx][y+dy] != '#' and area[x][y] != 'O':
        x += dx
        y += dy
        count += 1
    
    return x, y, count


def bfs(rx, ry, bx, by):
    visited_r = [[False] * M for _ in range(N)]
    visited_b = [[False] * M for _ in range(N)]
    q = deque()
    q.append((rx, ry, bx, by, 1))
    visited_r[rx][ry] = True
    visited_b[bx][by] = True

    
    while q:
        rx, ry, bx, by, depth = q.popleft()
        # 기울임 횟수가 10을 넘어가면 -1
        if depth > 10:
            return -1
        
        for i in range(4):
            nrx, nry, r_count = move(rx, ry, dx[i], dy[i])
            nbx, nby, b_count = move(bx, by, dx[i], dy[i])

            # 파란 구슬이 구멍에 도착 => 실패
            if area[nbx][nby] == 'O':
                continue
            # 빨간 구슬이 구멍에 도착 => 성공
            if area[nrx][nry] == 'O':
                return depth
            # 파란 구슬 위치 == 빨간 구슬 위치
            ## 더 많이 이동한 구슬이 양보한다.
            if (nbx == nrx) and (nby == nry):
                if r_count > b_count:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
            # 방문하지 않은 위치
            if not visited_r[nrx][nry] and not visited_b[nbx][nby]:
                visited_r[nrx][nry] = True
                visited_b[nbx][nby] = True
                q.append((nrx, nry, nbx, nby, depth+1))
    return -1

N, M = map(int, input().split())    # N: 행, M: 열
area = [list(map(str, input().strip())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 빨간 구슬, 파란 구슬 위치 찾기
for i in range(N):
    for j in range(M):
        if area[i][j] == 'R':
            rx, ry = i, j
            area[i][j] = '.'
        elif area[i][j] == 'B':
            bx, by = i, j
            area[i][j] = '.'

answer = bfs(rx, ry, bx, by)
print(answer)