1일 1커밋 !

1일 1PS 76일차!

📚 문제

[골드 1] - 구슬 탈출2

💡 풀이 과정

  • 10번 이내 움직임이라 DFS 를 사용해도 되지만 최소 탈출 경로이므로 BFS 를 사용해야한다.


  • 4가지 방향으로 구슬을 굴리고 R, B 를 지운 보드애서 벽이나 탈출구를 만날 때까지 같은 방향으로 이동한다.

  • 멈춘 구슬의 위치를 통해 visited 를 구현한다.

  • 여기서 4가지 경우의 수가 존재한다.
  1. 빨간 구슬만 탈출할 경우 (정답)
  2. 빨간 구슬과 파란 구슬이 같이 탈출할 경우
  3. 파란 구슬만 탈출할 경우
  4. 파란 구슬과 빨간 구슬이 같은 위치로 굴러갈 경우
    1. 파란 구슬이 앞서 있었을 경우
    2. 빨간 구슬이 앞서 있었을 경우
  • 1, 2, 3번은 각 구슬이 탈출구 앞에서 멈추었는 지 확인한다.
  • 1번이 정답이며 2, 3번은 모두 오답이므로 파란 구슬이 탈출할 경우는 모두 오답 처리한다.
  • 파란 구슬과 빨간 구슬이 같은 위치에 도착한다면 기울이는 방향에 따라 어느 구슬이 앞서 있었는 지 파악해 뒤따라온 구슬을 반대 방향으로 1 움직인다.
    • 이때 구슬은 다른 위치에서 굴러왔기 때문에 구슬 뒤 1칸은 항상 보장된다.

📌포인트

  • visited
    • ”“.join(map(str, temp[:-1])) 을 사용해서 요소들로만 문자열을 만들었지만,
    • 단순하게 str() 을 통해 배열 자체를 문자열로 바꾸는 방법이 더 좋은 것 같다.
  • cnt
    • cnt > 10 일 경우 continue 를 작성했더니 64%에서 계속해서 오류가 발생했다.
    • 다시 생각해보면 return (cnt + 1) 이기 때문에 11 이라는 값이 나올 수 있다는 뜻이다..!!
    • 이보다는 처음 cnt 를 1 로 설정해 queue 에 삽입하고 return cnt, cnt > 10 을 사용한다면 직관적인 의미로 사용할 수 있다.
      • pop 한 cnt 는 해당 로직을 포함해서 cnt 번 움직였다는 의미이므로..
      • 10번째 움직임을 허용하고 11번째 움직임이 들어온다면 continue ..

💻 코드


import sys
from collections import deque

input = sys.stdin.readline

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]

R, B = [], []

# 보드에서 공을 찾고 . 으로 업데이트
for i in range(N):
    for j in range(M):
        if board[i][j] == 'R':
            R = [i, j]
            board[i][j] = '.'
        if board[i][j] == 'B':
            B = [i, j]
            board[i][j] = '.'
            
    
def bfs():
    queue = deque()
    queue.append([R[0], R[1], B[0], B[1], 0])
    visited = set()
    
    while queue:
        temp = queue.popleft()
        
        # visited 혹은 10번 이상 움직였을 경우
        if str(temp[:-1]) in visited or temp[4] > 9:
            continue
            
        visited.add(str(temp[:-1]))
        
        rx, ry, bx, by, cnt = temp
        
        for i in range(4):
            nrx = rx
            nry = ry
            nbx = bx
            nby = by
            
            # 빨간 공 기울이기
            while board[nrx + dx[i]][nry + dy[i]] == '.':
                nrx += dx[i]
                nry += dy[i]
            
            # 파란 공 기울이기
            while board[nbx + dx[i]][nby + dy[i]] == '.':
                nbx += dx[i]
                nby += dy[i]
            
            # 빨간 공만 들어갈 수 있다면 return
            if board[nrx + dx[i]][nry + dy[i]] == 'O' and board[nbx + dx[i]][nby + dy[i]] != 'O':
                return cnt + 1
            
            # 파란 공이 들어갔다면 통과
            if board[nbx + dx[i]][nby + dy[i]] == 'O':
                continue
            
            # 같은 곳에 있는 경우 처음 위치가 뒤쳐진 공이 한칸 뒤로 이동한다.
            # 두 공은 다른 곳에서 출발했기 때문에 뒤돌아갈 1 칸은 보장된다.
            if nrx == nbx and nry == nby:
                # [1, 0] 이로 이동 시
                if i == 0:
                    if rx > bx:
                        nbx -= 1
                    else:
                        nrx -= 1

                # [0, 1] 이로 이동 시
                elif i == 1:
                    if ry > by:
                        nby -= 1
                    else:
                        nry -= 1
                
                # [-1, 0] 이로 이동 시
                elif i == 2:
                    if rx < bx:
                        nbx += 1
                    else:
                        nrx += 1
                
                # [0, -1] 이로 이동 시
                elif i == 3:
                    if ry > by:
                        nry += 1
                    else:
                        nby += 1
    
            queue.append([nrx, nry, nbx, nby, cnt + 1])

result = bfs()
if result:
    print(result)
else:
    print(-1)

업데이트:

댓글남기기

참고