[문제 출처]
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
baekjoon님이 만드신 '삼성 SW 역량 테스트 기출문제' 문제집을 풀기로 하고 만난 첫 번째 문제입니다!
역시 기출 문제여서 그런지 저에게는 상당히 난이도가 높았습니다😭
혹시나 테스트 케이스는 모두 통과하지만 반례를 찾지 못한 분이 계시다면 아래의 링크 속 반례를 시도하시는 걸 권합니다!!
(제가 해당 반례를 고려하지 못해서 실패를 했었거든요..ㅎㅎ)
링크: www.acmicpc.net/board/view/27629
이 문제는 상하좌우 적절히 구슬판을 움직여서 빨간색 구슬을 구멍으로 빼내고 그때 움직임의 횟수를 세는 문제입니다!
단, 파란색 구슬이 구멍을 통해 빠져나오면 실패이며 이 경우 -1을 출력합니다.
또한 최대 움직임 횟수는 10으로 제한됩니다.
저는 해당 문제를 DFS로 접근했습니다.
느낌상 탐색을 하는 문제인데 깊게 쭉쭉 들어가야 할 거 같았습니다!
생각의 과정은 대략 아래와 같습니다.
1. 현재 빨간 구슬의 위치를 기준으로 상하좌우 이동 후 파란 구슬도 같은 방향으로 이동
2. 빨간 구슬과 파란 구슬이 겹치지 않도록 위치 조정
3. 해당 위치에서 탐색을 계속 할지 판단
-3.1: 만약 움직임 후 어느 구슬도 위치에 변화가 없다면 탐색 중단(isStop = -1)
-3.2: 만약 파란 구슬이 구멍으로 들어갔다면 실패이므로 탐색 중단(isStop = -1)
-3.3: 파란 구슬이 안들어 갔다는 조건 하에 만약 빨간 구슬이 구멍으로 들어갔다면 성공이므로 탐색 중단(isStop = 1)
4. 새로 이동된 구슬의 위치를 계산한 후 탐색 중단 여부에 따라 다음 행동 판단
-4.1: 탐색 진행이라면 stack에 새로운 구슬 위치와 움직임 횟수를 push
-4.2: 탐색 중단 중 성공한 경우 answer와 값을 비교해서 움직임 횟수를 저장
5. stack이 비여있을 때까지 1 ~ 4까지 반복
코드가 매우 길고 지저분하지만 제가 짠 전체 코드는 아래와 같습니다😊
전체 코드
import sys
def move(curRed, curBlue, direction):
newRed = (curRed[0], curRed[1])
newBlue = (curBlue[0], curBlue[1])
isRedGoal = False
isBlueGoal = False
# 0 : 계속 진행
# 1 : 성공
# -1 : 실패
isStop = 0
if direction == "left":
for i in range(curRed[1]-1, -1, -1):
if mat[curRed[0]][i] == "#":
newRed = (curRed[0], i+1)
break
elif mat[curRed[0]][i] == "O":
isRedGoal = True
break
for i in range(curBlue[1]-1, -1, -1):
if mat[curBlue[0]][i] == "#":
newBlue = (curBlue[0], i+1)
break
elif mat[curBlue[0]][i] == "O":
isBlueGoal = True
break
if newRed == newBlue:
if curRed[1] < curBlue[1]:
# 레드 먼저 움직임
newBlue = (newBlue[0], newBlue[1]+1)
elif curRed[1] > curBlue[1]:
# 블루 움직임
newRed = (newRed[0], newRed[1]+1)
elif direction == "right":
for i in range(curRed[1]+1, M, 1):
if mat[curRed[0]][i] == "#":
newRed = (curRed[0], i-1)
break
elif mat[curRed[0]][i] == "O":
isRedGoal = True
break
for i in range(curBlue[1]+1, M, 1):
if mat[curBlue[0]][i] == "#":
newBlue = (curBlue[0], i-1)
break
elif mat[curBlue[0]][i] == "O":
isBlueGoal = True
break
if newRed == newBlue:
if curRed[1] < curBlue[1]:
# 블루 움직임
newRed = (newRed[0], newRed[1]-1)
elif curRed[1] > curBlue[1]:
# 레드 먼저 움직임
newBlue = (newBlue[0], newBlue[1]-1)
elif direction == "top":
for i in range(curRed[0]-1, -1, -1):
if mat[i][curRed[1]] == "#":
newRed = (i+1, curRed[1])
break
elif mat[i][curRed[1]] == "O":
isRedGoal = True
break
for i in range(curBlue[0]-1, -1, -1):
if mat[i][curBlue[1]] == "#":
newBlue = (i+1, curBlue[1])
break
elif mat[i][curBlue[1]] == "O":
isBlueGoal = True
break
if newRed == newBlue:
if curRed[0] < curBlue[0]:
# 레드 먼저 움직임
newBlue = (newBlue[0]+1, newBlue[1])
elif curRed[0] > curBlue[0]:
# 블루 먼저 움직임
newRed = (newRed[0]+1, newRed[1])
else:
for i in range(curRed[0]+1, N, 1):
if mat[i][curRed[1]] == "#":
newRed = (i-1, curRed[1])
break
elif mat[i][curRed[1]] == "O":
isRedGoal = True
break
for i in range(curBlue[0]+1, N, 1):
if mat[i][curBlue[1]] == "#":
newBlue = (i-1, curBlue[1])
break
elif mat[i][curBlue[1]] == "O":
isBlueGoal = True
break
if newRed == newBlue:
if curRed[0] < curBlue[0]:
# 블루 먼저 움직임
newRed = (newRed[0]-1, newRed[1])
elif curRed[0] > curBlue[0]:
# 레드 먼저 움직임
newBlue = (newBlue[0]-1, newBlue[1])
if curRed == newRed and curBlue == newBlue:
isStop = -1
if isBlueGoal == True:
isStop = -1
elif isRedGoal == True:
isStop = 1
return (newRed, newBlue, isStop)
N, M = map(int, sys.stdin.readline().strip().split())
mat = [ [e for e in sys.stdin.readline().strip()] for _ in range(N)]
#print(mat)
answer = -1
posRed = (0, 0)
posBlue = (0, 0)
directions = {
"left": (0, -1),
"right": (0, 1),
"top": (-1, 0),
"bottom": (1, 0)
}
for r in range(N):
for c in range(M):
if mat[r][c] == "R":
posRed = (r, c)
mat[r][c] = "."
elif mat[r][c] == "B":
posBlue = (r, c)
mat[r][c] = "."
stack = [ (posRed, posBlue, 0, "-") ]
while stack:
curRed, curBlue, movingCnt, prevDirection = stack.pop()
if movingCnt <= 9:
for d, pos in directions.items():
i, j = pos
if 0 <= curRed[0]+i < N and 0 <= curRed[1]+j < M:
# 구슬을 해당 방향으로 이동 시킴
newRed, newBlue, isStop = move(curRed, curBlue, d)
if isStop == 0:
# 스택에 append
stack.append((newRed, newBlue, movingCnt+1, d))
elif isStop == 1:
if answer == -1:
answer = movingCnt+1
else:
if answer > movingCnt+1:
answer = movingCnt+1
print(answer)
문제를 풀고 난 후
같은 언어의 다른 풀이들에 비해 저의 풀이는 속도 측면에서 느린 축에 속했습니다..!
여러 이유가 있겠지만 다른 풀이 들에서 눈에 띄는 차이는 DFS가 아닌 BFS로 문제를 접근한 것이었습니다.
*해당 문제의 분류를 보니 '너비 우선 탐색'에 속해있었습니다.
=> 추측이지만 너비 우선 탐색을 할 경우 최초의 성공이 최소 이동 횟수를 보장할 수 있을 거 같아요.
=> 따라서 최초의 성공 후 반복문을 바로 종료하게 되어 시간 단축의 효과가 있을 거 같습니다!
따라서 BFS로 해결을 해볼 생각입니다!
그러나 똑같은 문제를 푸는 것보다는 새로운 문제를 푸는 것이 좀 더 재밌으니
비슷한 시리즈인 '구슬 탈출'로 연습을 할 예정입니다ㅎㅎ
문제 링크: www.acmicpc.net/problem/13459
'PS > Python' 카테고리의 다른 글
| [백준] 20056 - 마법사 상어와 파이어볼(파이썬, Python) (0) | 2021.04.29 |
|---|---|
| [백준] 12100 - 2048 (Easy) (파이썬, Python) (0) | 2021.04.06 |
| [백준] 13305 - 주유소 (파이썬, Python) (0) | 2021.03.31 |
| [백준] 10816 숫자 카드 2 (파이썬, Python) (0) | 2021.03.31 |
| [백준] 15650 - N과 M (2) (파이썬, Python) (0) | 2021.03.30 |