백준 삼성 SW 역량 테스트 기출 문제
구슬탈출 2
어떤 카테고리의 문제인지 파악하는 것은 어렵지 않았던 문제이다. 다만 구현에서 조금 복잡한 난이도를 가지고 있었다. '왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다'라는 문구에서 네 가지 동작을 통해 뻗어나가는 탐색문제라는 사실을 유추할 수 있다. 다음과 같은 트리의 탐색을 떠올리면 된다.
노드 순서에 따라 움직일 때 조건에 맞는 , 길이가 가장 짧은 가지의 길이만 구하면 된다.
가령 예시 입력의
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######부분은 'root -> 좌 -> 하 -> 우 -> 하 ->좌' 노드가 조건을 만족 하므로 간선 길이인 5가 정답이 되는 셈이다. 따라서 BFS알고리즘을 이용해 트리를 탐색 해보려는 시도는 손쉽게 할 수 있으나, 조건이 많아 쉽지는 않았다.
백트래킹이 없고 난이도가 낮은 BFS기초 문제는 보통 탐색의 경로를 배열에 그려도 지장이 없다(ex.미로찾기).그러나 백트래킹을 고려하는 높은 난이도의 탐색은 일반적으로 배열(문제에서는 보드)에 경로를 표기해가며 조건을 판단하면 머리가 복잡해진다.
이상하게 백트래킹을 검색하면, 개념강의는 많은데 구현에 대해 확실한 공식을 제시하는 글이 적다고 느껴졌다. 나는 처음 이러한 문제를 마주했을 때 보드를 deepcopy로 복사해가며 각 동작마다의 보드를 queue에 집어 넣는 방식을 취했다. 그 방식으로 맞출 수 있는 문제도 아주 간혹 있었으나, 상식적으로 2차원 배열이 노드 수 만큼 생성되는 코드가 바람직할리도 없고 대부분 시간문제가 생겼다.
가령 root -> 상 -> 하 경로를 확인한다고 했을 때, 상 노드가 보드를 위로 한번 기울인 상태정보를 가지고 있도록 한 다음, 아래로 기울인 상태를 업데이트하고 저장하는게 좋을 것이라 생각한 것이다. 결론부터 말하자면, root -> 상 -> 하를 살필 때는 그냥 한 코드에서 root -> 상 ->하를 일일이 긋고 조건을 판단하는게 정답인 것으로 보인다. 더 나은 방법이 있는지는 모르겠지만 백트래킹의 구현에 있어서 본인은 이런 공식을 가지려고 한다.
결과적으로 이 문제를 비롯해 비슷한 유형의 백트래킹 문제를 마주치게 된다면 우선 탐색할 트리에 대해 생각해야하고(문제에서는 상하좌우 동작), 탐색할 경로를 일일이 그래프에 그리는게 아니라 경로만을 저장하고 매번 root상태에서 목표한 경로를 한번에 그어 조건을 확인해야 한다는 점을 생각해야 한다. 그리고 특히, 종료조건에 대해 빠짐없이 파악해야 한다. 이 문제에서는 다음을 고려해야 한다.
- 파란 구슬이 구멍에 빠지면 안 된다.(빨강이 먼저 빠졌다 해도)
- 10번 이하로 움직여서 빨간 구슬이 구멍에 빠지지 않으면 -1 출력
구현은 다음과 같다.
- queue 에 root node(아무것도 움직이지 않은 상태)를 append
- 일반적인 상하좌우 탐색 BFS알고리즘 실행
- 상하좌우를 탐색하고, 파랑구슬이 빠졌거나, 막다른 길이거나, 왔던 길로 돌아가는 경우 그 노드는 queue에 삽입하지 않는다.
- queue에 삽입하는 노드는 노드의 경로와 간선의 길이를 담은 리스트로 이뤄져있다.
- 빨강 구슬만 빠져 나오면 즉시 프로그램을 종료하며 간선 길이를 출력한다. 또는 간선길이가 10 을 넘으면 -1을 출력한다.
통과코드
from collections import deque
from copy import deepcopy
n, m = map(int, input().split())
board = list()
for i in range(n):
temp = list(input())
if 'B'in temp:
blue = [i,temp.index('B')]
if 'R' in temp:
red = [i,temp.index('R')]
board.append(temp)
queue = deque([[0]])
#0->하 1->상 2->좌 3->우 , 빨강구슬 통과시 1, 파랑구슬 통과 혹은 막다른 길 0, 경로 업데이트 -1
def move(moveList):
tempBoard = deepcopy(board)
tempBlue = deepcopy(blue)
tempRed = deepcopy(red)
answer = -1
for moving in moveList:
moved = False
if moving==0:
while tempBoard[tempBlue[0]+1][tempBlue[1]]=='.':
tempBlue[0]+=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]-1][tempBlue[1]]='.'
moved = True
while tempBoard[tempRed[0]+1][tempRed[1]]=='.':
tempRed[0]+=1
tempBoard[tempRed[0]][tempRed[1]]='R'
tempBoard[tempRed[0]-1][tempRed[1]]='.'
moved = True
if tempBoard[tempRed[0]+1][tempRed[1]]=='O':
tempBoard[tempRed[0]][tempRed[1]]='.'
moved = True
answer = 1
while tempBoard[tempBlue[0]+1][tempBlue[1]]=='.':
tempBlue[0]+=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]-1][tempBlue[1]]='.'
moved = True
if tempBoard[tempBlue[0]+1][tempBlue[1]]=='O':
moved = True
answer = 0
elif moving==1:
while tempBoard[tempBlue[0]-1][tempBlue[1]]=='.':
tempBlue[0]-=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]+1][tempBlue[1]]='.'
moved = True
while tempBoard[tempRed[0]-1][tempRed[1]]=='.':
tempRed[0]-=1
tempBoard[tempRed[0]][tempRed[1]]='R'
tempBoard[tempRed[0]+1][tempRed[1]]='.'
moved = True
if tempBoard[tempRed[0]-1][tempRed[1]]=='O':
tempBoard[tempRed[0]][tempRed[1]]='.'
moved = True
answer = 1
while tempBoard[tempBlue[0]-1][tempBlue[1]]=='.':
tempBlue[0]-=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]+1][tempBlue[1]]='.'
moved = True
if tempBoard[tempBlue[0]-1][tempBlue[1]]=='O':
moved = True
answer = 0
elif moving ==2:
while tempBoard[tempBlue[0]][tempBlue[1]-1]=='.':
tempBlue[1]-=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]][tempBlue[1]+1]='.'
moved = True
while tempBoard[tempRed[0]][tempRed[1]-1]=='.':
tempRed[1]-=1
tempBoard[tempRed[0]][tempRed[1]]='R'
tempBoard[tempRed[0]][tempRed[1]+1]='.'
moved = True
if tempBoard[tempRed[0]][tempRed[1]-1]=='O':
tempBoard[tempRed[0]][tempRed[1]]='.'
moved = True
answer = 1
while tempBoard[tempBlue[0]][tempBlue[1]-1]=='.':
tempBlue[1]-=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]][tempBlue[1]+1]='.'
moved = True
if tempBoard[tempBlue[0]][tempBlue[1]-1]=='O':
moved = True
answer = 0
else:
while tempBoard[tempBlue[0]][tempBlue[1]+1]=='.':
tempBlue[1]+=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]][tempBlue[1]-1]='.'
moved = True
while tempBoard[tempRed[0]][tempRed[1]+1]=='.':
tempRed[1]+=1
tempBoard[tempRed[0]][tempRed[1]]='R'
tempBoard[tempRed[0]][tempRed[1]-1]='.'
moved = True
if tempBoard[tempRed[0]][tempRed[1]+1]=='O':
tempBoard[tempRed[0]][tempRed[1]]='.'
moved = True
answer = 1
while tempBoard[tempBlue[0]][tempBlue[1]+1]=='.':
tempBlue[1]+=1
tempBoard[tempBlue[0]][tempBlue[1]]='B'
tempBoard[tempBlue[0]][tempBlue[1]-1]='.'
moved = True
if tempBoard[tempBlue[0]][tempBlue[1]+1]=='O':
moved = True
answer = 0
if moved:
return answer
else:
return 0
answer = 0
while queue: #BFS 실시
temp = queue.popleft()
movelist = temp[:-1]
time = temp[-1]
if time==10:
answer = -1
break
for i in range(4):
tempList = deepcopy(movelist)
#root 노드 혹은 되돌아가는 경로 방지
if tempList and ((tempList[-1]==0 and i==1) or (tempList[-1]==1 and i==0) or (tempList[-1]==2 and i==3) or (tempList[-1]==3 and i==2)):
continue
else:
tempList.extend([i, time+1])
if move(tempList[:-1])==1:
answer = time+1
queue.clear()
break
elif move(tempList[:-1])==0:
continue
else:
queue.append(tempList)
if answer:
print(answer)
else:
print(-1)상하좌우를 배열에 넣고 반복문을 돌리는 테크닉은 제안시간 안에 구현하지 못해 그냥 노가다 코드가 되었다. 사실상 푸는데만 초점이 맞춰져 있어 몹시 길지만, 실전환경에서는 이런녀석이 효용이 있을지도 모른다(?)
처음 쓰는 거라 횡설수설 하지만 꾸준히 쓰면 더 나아지지 않을까 싶다.
