13460. 구슬 탈출2

문제

코드

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def move(i, j, d):
    count = 0 # cnt는 두 구슬이 겹치려고 할 때 누가 먼저 왔는지 구분하기 위함
    while True:
        if arr[i+d[0]][j+d[1]] != '#' and arr[i][j] != 'O': #앞이 벽이거나, 현재가 탈출구가 아니면 계속 감
            i += d[0]
            j += d[1]
            count += 1
        else:
            break
    return i, j, count

def bfs(rx, ry, bx, by):
    q = [(rx, ry, bx, by, 1)]
    visited[rx][ry][bx][by] = 1

    while q:
        ri, rj, bi, bj, cnt = q.pop(0)
        if cnt > 10:
            break
        for k in range(4): #벽/출구 한칸 전까지만 이동
            rni, rnj, rmove = move(ri, rj, dirs[k])
            bni, bnj, bmove = move(bi, bj, dirs[k])

            if arr[bni][bnj] == 'O': #파란구슬이 도착하면 다른방향으로 계속
                continue
            if arr[rni][rnj] == 'O': #만약 ri, rj + k가 도착이면 성공
                return cnt

            if rni == bni and rnj == bnj: #같은 위치이면 move수가 많은 것을 한단계 뒤로 배치 = 뒤늦게 도착
                if rmove > bmove:
                    rni -= dirs[k][0]
                    rnj -= dirs[k][1]
                else:
                    bni -= dirs[k][0]
                    bnj -= dirs[k][1]

            if visited[rni][rnj][bni][bnj] == 0:
                q.append((rni, rnj, bni, bnj, cnt+1))
                visited[rni][rnj][bni][bnj] = 1
    return -1

n, m = map(int, input().split(" "))
arr = []
visited = [[[[0]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
red, blue = (), ()
for i in range(n):
    temp = list(input())
    arr.append(temp)
    if 'R' in temp:
        red = (i, temp.index('R'))
    if 'B' in temp:
        blue = (i, temp.index('B'))

print(bfs(red[0], red[1], blue[0], blue[1]))

풀이

구현, 시뮬레이션이 너무 어렵다. 특히 삼성 구현 토나온다🤮. 기출문제라 풀어봤는데 이해 못해서 겨우겨우 다른사람 코드 보면서 이해했다.

문제를 풀면서 생각해봐야할 것은 다음과 같다

• 벽, 출구가 아닐때 어떤 방법으로 끝까지 이동시킬것인가?
• 기울이면서 두 구슬이 겹칠때 어떻게 판단해서 위치를 나눌것인가?
• 좌우좌우 계속 무한루프 기울이지 않으려면 어떻게 판단?
• 파란구슬이 먼저 도착한다면 어떻게 처리해줘야하는지?

출구가 아닐때 끝까지 이동시키는 방법은 dir을 벽이 나오기 전까지, 출구가 아닐때까지 계속 더해주는 것 -> move 함수로 구현, 무브 함수는 초기 위치와 앞으로 갈 방향을 받는다.

기울이면서 두 구슬이 겹칠 때 어떻게 판단하는지 ? -> move할때 몇칸을 이동했냐를 보면 됨. 이동한 칸 수가 많은 색이 더 멀리서 왔다는 뜻이므로 나중에 위치하게 됨(move 결과상으로 같은 자리에 있다가, bfs에서 확인해서 한칸 뒤로 보내주면 된다)

좌우좌우 등 무한루프에 빠지지 않으려면? -> visited 배열을 활용해서 현재 색상의 구슬이 이미 방문한 끝인지 확인한다.

파란구슬이 먼저 도착한다면? -> continue 하여 우선 다른 방법을 찾아보는데, 어차피 이리저리 움직이다 보면 10번을 넘겨서 파란구슬일때는 답이 안나온다!

references

• https://na982.tistory.com/82?category=145346
  설명이 잘 되어있고 강의도 있다.