[삼성sw역량테스트 - 기출] 구슬 탈출2

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

#구슬 탈출2
from sys import stdin
from collections import deque
input = stdin.readline

n,m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]
check = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()

def init():
    rx, ry, bx, by = [0] * 4
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                rx, ry = i, j
            if graph[i][j] == 'B':
                bx, by = i, j
    q.append((rx, ry, bx, by, 0))
    check[rx][ry][bx][by] = True
    
def move(x, y, dx, dy, c):
    while graph[x + dx][y + dy] != '#' and graph[x][y] != 'O':
        x += dx
        y += dy
        c += 1
        
    return x, y, c

def bfs():
    while q:
        rx, ry, bx, by, count = q.popleft()
        if count >= 10:
            print(-1)
            return
        
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0)
            nbx, nby, bc = move(bx, by, dx[i], dy[i], 0)

            if graph[nbx][nby] == 'O':
                continue
            if graph[nrx][nry] == 'O':
                print(count + 1)
                return
            if nrx == nbx and nry == nby:
                if rc > bc:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
            if not check[nrx][nry][nbx][nby]:
                check[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, count+1))
    print(-1)

init()
bfs()

 

 

구슬을 굴리면서 빨간 구슬과 파란 구슬의 이동 거리를 비교해 겹치지 않도록 처리하는 것이 아이디어.

생각보다 어려웠는데 이 분 블로그를 참고했더니 어떻게 풀지 감이 확 잡혔다.

rebas.kr/725

BOJ 13460 · 구슬 탈출 2

 

---

삼성 서류를 합격했다.

돌아오는 일요일에 SW역량테스트를 보게 되어 급하게 DFS/BFS문제를 풀어야 한다..

백준에 있는 기출문제를 다 풀고 가는게 나의 목표..!

 

첫 문제가 구슬탈출2인데 하필 정답률 25%되는 어려운 문제라 힘들었다..