하나씩 점을 찍어 나가며문제
구슬 탈출 2 (https://www.acmicpc.net/problem/13460)
풀이
1. 초기 접근
- 문제조건 해석
- 판이 주어지고, 스텝에 따라 판 위에 구슬의 위치가 규칙적으로 달라진다.
- 목표하는 위치에 도달하기 위한 "최소" 스텝을 구해야 한다.
- BFS 문제다.
- 알고리즘
- 이번 문제는 조금 까다로웠는데, step by step 으로 하나씩 코드화 해보자.
1) 먼저 기본적인 입력과 BFS 들을 만든다.
메인 코드는 아래와 같다.
from collections import deque
dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]
# n, m을 입력받고, board에 판을 저장한다.
n, m = list(map(int, input().split()))
board = [list(input()) for _ in range(n)]
# 빨간 구슬과 파란 구슬의 위치를 저장해둔다.
red, blue = None, None
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
red = (i, j)
elif board[i][j] == 'B':
blue = (i, j)
# bfs 함수에 두 구슬의 위치를 건네주면, 우리가 원하는 최소 스텝을 반환받는다.
print(bfs(red, blue))bfs() 함수의 코드의 기본 틀은 아래와 같다.
def bfs(red, blue):
q = deque([(red, blue)])
visited = set([(red, blue)])
step = 0
while q and step <= 10:
size = len(q)
for _ in range(size):
red, blue = q.popleft()
###########################
# 채워야 하는 부분 #
###########################
step += 1
return -1일단 여기까지는 쉽게 짤 수 있다.
이후에 할 일은, 채워야할 부분으로 표시한 부분을 채우는 일이다.
2) 각 4가지의 방향에 따라, 각 구슬이 이동할 다음 좌표를 구한다.
먼저 크게, 4가지 방향으로 우리는 판을 기울일 수 있다.
그리고 한번 정한 방향은 빨간 구슬과 파란 구슬, 두 구슬 모두의 다음 방향이 된다.
자 이제 각 구슬의 이동을 트래킹해보자.
예를 들어, 오른쪽으로 기울인다고 해보자. 그럼 오른쪽으로 이동할 것이다.
현재가 (x, y) 였다면 (x, y+1) 로 이동할 것이다.
그럼 얼마나 이런 이동을 반복할 것인가?
다음 이동하려는 좌표가 빈 공간(.) 일 경우, 해당 방향으로 계속해서 이동해야 한다.
한편, 다음 이동하려는 좌표가 벽(#) 이거나 탈출구멍(O) 일 경우, 이동을 멈춰야 한다. 그리고 그 좌표가 최종 이동 좌표가 된다.
여기까지 생각하면, 다음과 같이 코딩할 수 있다.
def bfs(red, blue):
...
for _ in range(size):
red, blue = q.popleft()
# 기울이는 방향은 총 4가지다.
for dx, dy in zip(dxs, dys):
# 빨간 구슬을 먼저 움직인다.
x, y = red
nx, ny = x + dx, y + dy
while True:
if board[nx][ny] == '.':
x, y = nx, ny
nx, ny = nx + dx, ny + dy
elif board[nx][ny] == 'O':
x, y = nx, ny
break
else:
break
next_red = (x, y)
# 그 다음 파란 구슬을 움직인다.
# 코드는 위에 빨간 구슬이 움직인 것과 같다.
x, y = blue
nx, ny = x + dx, y + dy
while True:
if board[nx][ny] == '.':
x, y = nx, ny
nx, ny = nx + dx, ny + dy
elif board[nx][ny] == 'O':
x, y = nx, ny
break
else:
break
next_blue = (x, y)
step += 1
return -13) 불가능한 경우, 가능한 경우를 생각하여 BFS 큐에다가 넣어주자
먼저, 위 움직임에서 불가능한 경우는 어떤 경우일까?
파란색 구슬을 움직이는 중에, 다음 좌표가 탈출 구멍(O) 인 경우, 파란 구슬도 빠져버리는 경우이니, 이렇게 기울이는 경우는 제외해야 한다. 따라서, 별도의 is_possible 이라는 변수를 두어, 이렇게 빠져버리는 경우인지 아닌지 확인해야 한다.
한편, 우리는 "최소 횟수" 를 구하고 있으므로, 방문한 케이스를 또 방문할 필요가 없다. 이를 visited 로 해결하자.
def bfs(red, blue):
...
for _ in range(size):
...
for dx, dy in zip(dxs, dys):
is_possible = True
# 빨간 구슬을 먼저 움직인다.
...
next_red = (x, y)
# 그 다음 파란 구슬을 움직인다.
...
while True:
...
elif board[nx][ny] == 'O':
is_possible = False
break
...
next_blue = (x, y)
# 현재 경우가 가능한지, 방문한 적은 없는지 체크하고 BFS 큐에 다음 좌표를 넣어준다.
if is_possible and (next_red, next_blue) not in visited:
q.append((next_red, next_blue))
visited.add((next_red, next_blue))
step += 1
return -1하는 김에, 지금 탈출 구문도 넣어주자. BFS queue 에서 꺼냈을 때, 빨간공의 좌표가 탈출 구멍 좌표라면 탈출에 성공한 것이다.
def bfs(red, blue):
...
while q:
for _ in range(size):
# 큐에서 끄낸 빨간공의 좌표에 탈출 구멍이 있는 경우, step을 반환하고 끝낸다.
if board[red[0]][red[1]] == 'O':
return step
...5) 예외 케이스들을 생각해본다.
이 예외케이스들을 생각하며 해야하기 때문에 조금 골치가 아픈데, 첫 번째로 다음과 같은 케이스다.
생각해봐야 하는 케이스 1
3 10
##########
#.O....RB#
##########위 코드로 이 케이스를 수행하면, 빨간 구슬이 이동할 때에는 문제가 없다.
그런데, 파란 구슬이 이동할 때에 문제가 있다. 왼쪽으로 기울인다고 하자. 이 때 파란구슬은 다음 이동 좌표로 R 을 만나게 되는데, 위 코드를 보면 우리는 이 경우에 대해 처리해준적이 없다. 심지어, 빨간구슬은 이미 이동했기 때문에 저 위치에 있지 않다. 하지만 우리는 판(board)를 수정한적이 없다. 따라서 BFS가 아무리 진행되도 판(board)은 초기 상태 그대로인 셈이다.
이 경우를 어떻게 해결하면 좋을까 생각하다가, 애초에 우리는 빨간 구슬과 파란 구슬의 이동하는 좌표만 트래킹하며 BFS queue(q) 에 넣고 있다는 사실을 발견했다. 그런데 지금 문제는 판(board) 자체에 있는 R 과 B 가 문제니, 이를 아예 판에서 없애버리면 된다. 즉, R 과 B를 발견하면 . 로 바꿔준다.
따라서 위 코드에서 해당부분을 다음과 같이 수정한다.
red, blue = None, None
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
red = (i, j)
board[i][j] = '.'
elif board[i][j] == 'B':
blue = (i, j)
board[i][j] = '.'생각해봐야 하는 케이스 2
5 7
#######
####O##
####.##
#R...B#
#######두 번쨰로 생각해봐야 하는 케이스는 위 경우인데, 오른쪽으로 기울인다고 생각해보자.
먼저, 빨간 구슬이 오른쪽으로 쭈우욱 움직이는데, 우리는 판(board) 에서 B 를 . 로 바꿨으니 파란 구슬이 있는 위치까지 움직여 결과적으로 파란 구슬과 겹치게 된다. 이는 구슬이 겹치게 되는 이상한 결과다.
이 케이스를 고려하여, 각 구슬이 얼마나 움직이는지 red_step, blue_step 을 두어, 후에 두 구슬의 다음 움직일 위치가 겹치는 경우, 더 적게 움직이는 쪽을 우선하여 위치를 고려해줘야 한다.
이를 코드화하면 다음과 같다.
...
for dx, dy in zip(dxs, dys):
...
while True:
if board[nx][ny] == '.':
...
# 빨간 구슬이 얼마나 움직였는지 체크해논다.
red_step += 1
...
...
while True:
if board[nx][ny] == '.':
...
# 파란 구슬이 얼마나 움직였는지 체크해논다.
blue_step += 1
...
...
# 두 구슬의 다음 이동 좌표가 같은 경우, 좌표를 조정해준다.
if next_red == next_blue:
if red_step < blue_step:
a, b = next_blue
next_blue = (a-dx, b-dy)
else:
a, b = next_red
next_red = (a-dx, b-dy)
...코드
전체적인 코드는 다음과 같다.
from collections import deque
dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]
def bfs(red, blue):
q = deque([(red, blue)])
visited = set([(red, blue)])
step = 0
while q and step <= 10:
size = len(q)
for _ in range(size):
red, blue = q.popleft()
if board[red[0]][red[1]] == 'O':
return step
for dx, dy in zip(dxs, dys):
is_possible = True
x, y = red
nx, ny = x + dx, y + dy
red_step = 0
while True:
if board[nx][ny] == '.':
x, y = nx, ny
nx, ny = nx + dx, ny + dy
red_step += 1
continue
elif board[nx][ny] == 'O':
x, y = nx, ny
red_step += 1
break
else:
break
next_red = (x, y)
x, y = blue
nx, ny = x + dx, y + dy
blue_step = 0
while True:
if board[nx][ny] == '.':
x, y = nx, ny
nx, ny = nx + dx, ny + dy
blue_step += 1
elif board[nx][ny] == 'O':
is_possible = False
blue_step += 1
break
else:
break
next_blue = (x, y)
if next_red == next_blue:
if red_step < blue_step:
a, b = next_blue
next_blue = (a-dx, b-dy)
else:
a, b = next_red
next_red = (a-dx, b-dy)
if is_possible and (next_red, next_blue) not in visited:
q.append((next_red, next_blue))
visited.add((next_red, next_blue))
step += 1
return -1
n, m = list(map(int, input().split()))
board = [list(input()) for _ in range(n)]
red, blue = None, None
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
red = (i, j)
board[i][j] = '.'
elif board[i][j] == 'B':
blue = (i, j)
board[i][j] = '.'
print(bfs(red, blue))제출하면, 맞았습니다가 나온다.
그런데 위 코드에서 중복되는 부분이 있어, 이 부분을 좀 더 리팩토링하여 보았다.
중복을 제거하여 리팩토링한 코드
from collections import deque
dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]
def bfs(red, blue):
q = deque([(red, blue)])
visited = set([(red, blue)])
step = 0
while q and step <= 10:
size = len(q)
for _ in range(size):
red, blue = q.popleft()
if board[red[0]][red[1]] == 'O':
return step
for dx, dy in zip(dxs, dys):
is_possible = True
next_ball = [-1, -1]
ball_step = [0, 0]
for ball_idx, ball in enumerate([red, blue]):
x, y = ball
nx, ny = x + dx, y + dy
while True:
if board[nx][ny] == '.':
x, y = nx, ny
nx, ny = nx + dx, ny + dy
ball_step[ball_idx] += 1
continue
elif board[nx][ny] == 'O':
if ball == blue:
is_possible = False
else:
x, y = nx, ny
ball_step[ball_idx] += 1
break
else:
break
next_ball[ball_idx] = (x, y)
if next_ball[0] == next_ball[1]:
if ball_step[0] < ball_step[1]:
a, b = next_ball[1]
next_ball[1] = (a-dx, b-dy)
else:
a, b = next_ball[0]
next_ball[0] = (a-dx, b-dy)
next_ball = tuple(next_ball)
if is_possible and next_ball not in visited:
q.append(next_ball)
visited.add(next_ball)
step += 1
return -1
n, m = list(map(int, input().split()))
board = [list(input()) for _ in range(n)]
red, blue = None, None
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
red = (i, j)
board[i][j] = '.'
elif board[i][j] == 'B':
blue = (i, j)
board[i][j] = '.'
print(bfs(red, blue))그렇게 깔끔한 코드는 아니지만, 이전보다는 중복된 코드가 덜 보인다.
'취업과 기본기 튼튼 > 코딩 테스트 노트' 카테고리의 다른 글
| [BOJ] 16235. 나무 재테크 (2) | 2019.04.10 |
|---|---|
| [BOJ] 16236. 아기 상어 (1) | 2019.04.10 |
| [BOJ] 1964. 소수 경로 (0) | 2019.04.08 |
| [BOJ] 2636. 치즈 (0) | 2019.04.08 |
| [BOJ] 13913. 숨바꼭질 4 (0) | 2019.04.07 |