문제 링크

구슬 탈출 2

문제 설명

N*M 크기의 보드에 빨간 구슬과 파란 구슬을 넣어서 빨간 구슬만 구멍으로 빠져나오게 하려고 한다. 구슬은 각각 1칸을 차지하고, 중력을 이용해서 상하좌우로 기울여서 움직인다. 구슬은 동시에 움직인다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

문제 풀이

아직 dfs 틀이 더 익숙하고, 사실 bfs의 큐에 어떤 값을 푸쉬해야될지 모르겠어서 일단 dfs로 도전했다.

시도 1 - dfs

처음에는 이런식으로 접근하려고 했다. 근데 간과한 것 ,,
1. 구슬 두개 모두 벽에 닿아서 더 이상 움직이지 않는 경우
2. 이동하다가 다른 구슬을 만났을때
3. 보드의 값을 직접 조작했기 때문에 dfs 돌고난 뒤 다시 map과 빨간공, 파란공의 좌표를 재설정 해줘야함

2는 구슬이 일직선 상에 있을때의 경우를 나눠서 해보려고 했는데 풀다보니까 이건 아닌 것 같았다 ^_ㅠ ;
하루종일 잡고 있다가 결국 https://inspirit941.tistory.com/180 님의 포스팅 참고,,

시도 2 - dfs

포인트는

1. 더 이상 움직이지 않는 경우
   -> move를 실행한 결과 좌표값과 이전 좌표값이 같으면 continue
2. 보드의 값을 직접 조작하는 것이 아닌 따로 저장하기 !!!
   -> 처음에 Map을 입력받을 때 R,B가 아닌 .로 재설정해줘야한다.
3. 겹치는 두 공에 대해서는
   -> 두 공이 각각 이동한 거리를 count해서 더 멀리서 출발한 공을 한칸 뒤로 뺀다 이런 생각 엌캐하지

import sys

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

n, m = map(int, input().split())
Map = []
red = []
blue = []
answer = 11

for i in range(n):
    tmp = list(input().strip())
    for j in range(m):
        if tmp[j] == 'R':
            red = (i,j)
            tmp[j] = '.'
        elif tmp[j] == 'B':
            blue = (i,j)
            tmp[j] = '.'
    Map.append(tmp)

#좌표가 범위 내에 있는지 검사
def in_bound(x, y):
    if x in range(0, n) and y in range(0,m):
        return True
    else:
        return False

#보드를 dir방향으로 기울이기
def move(red_pos, blue_pos, dir):
    red_x, red_y = red_pos
    blue_x, blue_y = blue_pos
    r_cnt, b_cnt = 0, 0
    r_out, b_out = False, False

    #빨간공 움직이기
    nx, ny = red_x+dx[dir], red_y+dy[dir]
    while in_bound(nx, ny):
        r_cnt += 1
        #벽이면 이동 전 좌표 리턴하기
        if Map[nx][ny] == '#':
            red_pos = (red_x, red_y)
            r_cnt -= 1
            break
        #구멍에 빠졌을때
        elif Map[nx][ny] == 'O':
            red_pos = (nx, ny)
            r_out = True
            break
        #아니면 전진
        else:
            red_x, red_y = nx, ny
            nx, ny = red_x + dx[dir], red_y + dy[dir]

    #파란공 움직이기
    nx, ny = blue_x+dx[dir], blue_y+dy[dir]
    while in_bound(nx, ny):
        b_cnt += 1
        #벽이면 이동 전 좌표 리턴하기
        if Map[nx][ny] == '#':
            blue_pos = (blue_x, blue_y)
            b_cnt -= 1
            break
        elif Map[nx][ny] == 'O':
            blue_pos = (nx, ny)
            b_out = True
            break
        else:
            blue_x, blue_y = nx, ny
            nx, ny = blue_x + dx[dir], blue_y + dy[dir]

    #둘다 빠져나왔으면 바로 리턴
    if r_out == b_out == True:
        return (red_pos, blue_pos)

    #같은 위치에 있으면
    if red_pos == blue_pos:
        #빨간공이 더 앞에 있었으면
        if r_cnt < b_cnt:
            blue_pos = (blue_x-dx[dir], blue_y-dy[dir])
        else:
            red_pos = (red_x-dx[dir], red_y-dy[dir])
    return (red_pos, blue_pos) 

def dfs(red_pos, blue_pos, count):
    global answer
    #10번 넘어가면
    if count > 10:
        return
    #파란공이 구멍으로 빠진 경우 -> 실패
    if Map[blue_pos[0]][blue_pos[1]] == 'O':
        return
    #빨간공이 구멍으로 빠진 경우 -> 성공
    if Map[red_pos[0]][red_pos[1]] == 'O':
        answer = min(answer, count)
        return

    for i in range(4):
        #기울이기
        r_pos, b_pos = move(red_pos, blue_pos, i)
        #안움직였으면
        if r_pos == red_pos and b_pos == blue_pos:
            continue
        dfs(r_pos, b_pos, count+1)

dfs(red, blue, 0)

if answer == 11:
    print(-1)
else:
    print(answer)

시도 3 - bfs

최소 거리이기 때문에 bfs로 푸는게 더 효율적이라서 다들 bfs로 풀었더라,,

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())
Map = []
red = []
blue = []
visited = [[0]*100 for _ in range(100)]
answer = 11

for i in range(n):
    tmp = list(input().strip())
    for j in range(m):
        if tmp[j] == 'R':
            red = (i, j)
            tmp[j] = '.'
        elif tmp[j] == 'B':
            blue = (i, j)
            tmp[j] = '.'
    Map.append(tmp)

def in_bound(x, y):
    if x in range(0, n) and y in range(0, m):
        return True
    else:
        return False

#방향 i로 기울이기
def move(r_pos, b_pos, i):
    red_x, red_y = r_pos
    blue_x, blue_y = b_pos
    r_out, b_out = False, False
    r_cnt, b_cnt = 0, 0

    nx, ny = red_x+dx[i], red_y+dy[i]
    r_cnt += 1
    while in_bound(nx, ny):
        #벽을 만나면
        if Map[nx][ny] == '#':
            r_pos = (nx-dx[i], ny-dy[i])
            r_cnt -= 1
            break
        #구멍에 빠지면
        elif Map[nx][ny] == 'O':
            r_pos = (nx, ny)
            r_out = 1
            break
        else:
            red_x, red_y = nx, ny
            nx, ny = nx+dx[i], ny+dy[i]
            r_cnt += 1

    nx, ny = blue_x+dx[i], blue_y+dy[i]
    b_cnt += 1
    while in_bound(nx, ny):
        # 벽을 만나면
        if Map[nx][ny] == '#':
            b_pos = (nx - dx[i], ny - dy[i])
            b_cnt -= 1
            break
        # 구멍에 빠지면
        elif Map[nx][ny] == 'O':
            b_pos = (nx, ny)
            b_out = True
            break
        else:
            blue_x, blue_y = nx, ny
            nx, ny = nx + dx[i], ny + dy[i]
            b_cnt += 1

    #둘다 구멍에 빠지면
    if r_out == b_out == True:
        return r_pos, b_pos

    #같은 위치에 있으면
    if r_pos == b_pos:
        if r_cnt < b_cnt:
            b_pos = (b_pos[0]-dx[i], b_pos[1]-dy[i])
        else:
            r_pos = (r_pos[0]-dx[i], r_pos[1]-dy[i])

    return r_pos, b_pos


def bfs(red_pos, blue_pos):
    queue = deque([[red_pos, blue_pos, 0]])

    while queue:
        #print(queue)
        red_pos, blue_pos, count = queue.popleft()
        if count > 10:
            continue
        if Map[blue_pos[0]][blue_pos[1]] == 'O':
            continue
        if Map[red_pos[0]][red_pos[1]] == 'O':
            print(count)
            return
        else:
            for i in range(4):
                r_pos, b_pos = move(red_pos, blue_pos, i)
                if r_pos == red_pos and b_pos == blue_pos:
                    continue
                queue.append([r_pos, b_pos, count+1])
    print(-1)
bfs(red, blue)

사실 문제의 포인트가 bfs나 dfs가 아니라 움직일때의 처리라 한번 풀고 나니까 bfs로는 금방 풀 수 있었다.