BOJ-13460 구슬탈출2 - 알고리즘 복습 1일차

https://www.acmicpc.net/problem/13460

 

 

문제 목표

판을 기울여가면서 빨간공만 빠뜨리기 위한 최소 시행 구하기 문제풀이

 

 

아이디어

1. 판에 크기에 해당하는 리스트를 만들기

2. 각각 상하좌우로 공을 옮기는 메소드를 만듬

3. 완전탐색으로 모든 경우를 시행해봄

 

 

처음 코드 (실패)

r,c = map(int, input().split(" "))
redLoc = [-1,-1]
blueLoc = [-1,-1]

board = [list(input()) for _ in range(r)]

def swap(loc1, loc2, M):
    ### loc1 과 loc2는 튜플
    temp = M[loc2[0]][loc2[1]]
    M[loc2[0]][loc2[1]] = M[loc1[0]][loc1[1]]
    M[loc1[0]][loc1[1]] = temp


def findBlock(loc,t, M):
    plus = 0
    result = [-1,-1]
    if t == 'L':
        for i in range(loc[1]-1,-1,-1):
            if M[loc[0]][i] == 'O' :
                return [-2, -2]
            if M[loc[0]][i] == 'B' or M[loc[0]][i] == 'R':
                plus = 1
            if M[loc[0]][i] == '#' :
                result[0] = loc[0]
                result[1] = i+1+plus
                break
    elif t == 'R':
        for i in range(loc[1]+1, c):
            if M[loc[0]][i] == '0' :
                return [-2, -2]
            if M[loc[0]][i] == 'B' or M[loc[0]][i] == 'R':
                plus = 1
            if M[loc[0]][i] == '#' :
                result[0] = loc[0]
                result[1] = i-1-plus
                break
    elif t == 'U':
        for i in range(loc[0]-1, -1, -1):
            if M[i][loc[1]] == '0' :
                return [-2, -2]
            if M[i][loc[1]] == 'B' or M[i][loc[1]] == 'R':
                plus = 1
            if M[i][loc[1]] == '#' :
                result[0] = i+1+plus
                result[1] = loc[1]
                break
    elif t == 'D':
        for i in range(loc[0]+1,r):
            if M[i][loc[1]] == '0' :
                return [-2, -2]
            if M[i][loc[1]] == 'B' or M[i][loc[1]] == 'R':
                plus = 1
            if M[i][loc[1]] == '#' :
                result[0] = i-1-plus
                result[1] = loc[1]
                break
    else:
        print("findBlock error")
        return (-1,-1)
    return result

def findBall():
    global redLoc
    global blueLoc
    count = 0
    for i in range(r):
        for j in range(c):
            if board[i][j] == "R":
                redLoc = [i,j]
                count +=1
            if board[i][j] == "B":
                blueLoc = [i,j]
                count +=1
            if count == 2:
                break

def move(redLoc, blueLoc,t,M):

    loc1 = findBlock(redLoc,t,M)
    swap(redLoc, loc1,M)
    redLoc = loc1

    loc2 = findBlock(blueLoc,t,M)
    swap(blueLoc, loc2,M)
    blueLoc = loc2

    if loc1 == [-2,-2] and loc2 == [-2,-2]:
        return -1

    if loc1 == [-2,-2]:
        return 1
    elif loc2 == [-2,-2]:
        return -1
    else:
        return 0


findBall()

mode = ['L','R','U','D']
minlevel = 10

def simul(level, result, M):

    global minlevel
    if result == 1:
        if level < minlevel:
            minlevel = level
    if result == -1 or level >= 2:
        return -1
    else:
        startRed = redLoc
        startBlue = blueLoc
        print(level)
        print(M)
        for t in mode:
            simul(level+1, move(startRed,startBlue,t,M), M)

simul(0,0,board)

 

복습 1일차라 구현에만 집중에서 처음 풀이를 작성했다.

이때의 목표는 백트래킹으로 직접 보드상에서 공을 옮기면서 몇단계에서 공이 빠지는지 확인하고 싶었다.

 

구현하고 보니 여러가지 문제가 생겼다.

 

1. 각 경우의 수에서 보드의 상태를 어떻게 유지할건가?

탐색 깊이가 0일 때의 보드의 상태와 상하좌우 움직였을때의 보드의 상태는 각각 다른데 이를 전역적으로 한 보드가지고 하기 어렵다는 것을 마지막에 알았다. 그렇다고 각 단계를 깊은 복사한다면 메모리가 감당이 안돼 풀이의 방향이 잘못됐다는것을 알았다.

그리고 매개변수로 배열을 넘기면 옅은 복사가 되는 것을 저번 알고리즘 복습할때 가변, 불변을 공부했었는데 코드를 치는 중에 생각하는 것이 어려웠다. 이는 내가 적었던 글과 다른 글을 더 보면서 다시 복습했다.

Python - 함수에 배열을 인자로 전달할 때

 

2. 빨간공의 위치와 파란공의 위치를 어떻게 관리할 것인가?

 

초기에 보드판을 보면서 공의 위치를 저장했는데 이후에 이를 어떻게 업데이트해야할지 감이 잡히지 않았다. 전역변수 하나로 두면 계속 그 후의 탐색과정에서 엉키게 되는데 이를 어떻게 제어해야할지 감이 잡히지 않았다.

 

 

이 2가지 어려움을 생각하며 풀이과정을 검색했고 가장 나에게 맞는 풀이법을 탐색했다.

[백준(BOJ)] 13460번 : 구슬 탈출 2 - PYTHON[파이썬]

 

해당 풀이를 보면서 많은 것을 느낄 수 있었다.

첫번째 의문은 지도상에 구슬을 컨트롤하기보단 지도는 고정해두는 방식으로 두번째 의문은 큐와 방문을 저장해두는 배열로 해결하면 된다는 것을 알았다. 그리고 방향배열을 두고 움직일 인덱스를 찾는 함수에서 while문을 사용해 공을 옮길 위치를 찾는 로직이 인상깊었다.

이 외에도 나는 공을 옮길 좌표를 구하는 함수를 정의할때 공이 목적지에 도착하면 [-2,-2] 를 줘서 추후 이걸로 성공 여부를 판별하려했는데 그럴 필요없이 그냥 좌표 그대로 마지막에 확인하는 것이 로직상 깔끔해진다는걸 알았다.

 

알고리즘에 꽤나 자신이 있었는데 알고리즘을 하지 않는 시간동안 많이 퇴화했음을 느꼈다.

이 문제는 틀린 상태로 두고 추후 탐색알고리즘을 복습한 후 다시 풀어보기로 마음먹었다.

 

정리

1. 보드판은 고정해둔다.

2. 빨간 , 파란 공의 위치를 저장해두고 이 위치로 bfs, dfs, 백트래킹 같은 탐색 알고리즘을 적용한다.

 

*최단횟수를 구하기때문에 bfs가 유리하고 백트래킹을 적용하기엔 가지치기 기준이 명확하지 않아 bfs가 옳은 접근법이다.