✔️ 문제 풀이
.
◾ 값 입력받기 & R, B 구슬 위치 파악
n, m = map(int, input().split())
rx, ry, bx, by = 0, 0, 0, 0
ru, bu = False, False
matrix = []
for i in range(n):
col = list(input())
if not ru and 'R' in col:
rx = col.index('R')
ry = i
ru = True
if not bu and 'B' in col:
bx = col.index('B')
by = i
bu = True
matrix.append(col)
matrix[ry][rx] = '.'
matrix[by][bx] = '.'n,m,matrix값을 입력받는다R과B구슬의 좌표를 파악하기 위한 변수 선언- 구슬의 좌표가 업데이트 되었는지 파악하기 위한 변수
ru,bu선언(조금이라도 실행시간을 줄이기 위해) - 행을 입력받은 후 구슬의 좌표를 입력받은 적 없으면 해당 구슬의 인덱스를 찾아
x,y좌표 업데이트 - 두 구슬의 좌표를 찾았으면 해당 위치는
.로 변경한다
.
◾ bfs 탐색에 활용하기 위한 변수 선언
queue = deque()
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited = []
visited.append([rx, ry, bx, by])visited배열을 다음과 같이 선언한 이유?
◽ 처음엔 방문 확인을 굳이 해야하는지 헷갈렸으나, 반드시 답이 있는 경우가 아니기 때문에 방문체크를 하지 않으면 무한루프가 발생할 수도 있음
◽ 두 개의 좌표를 동시에 방문한 적이 있는가를 체크하기 위해[rx, ry, bx, by]값을 한 번에 저장함
.
◾ 주어진 방향에 따라 구슬의 위치를 변경하는 moveTo 함수
def moveTo(rrx, rry, bbx, bby, z):
# 처음 주어졌던 구슬들의 좌표를 기억한다
orrx, orry, obbx, obby = rrx, rry, bbx, bby
# 이동불가능한 곳을 만날때까지 구슬의 위치를 이동
while matrix[rry][rrx] == '.':
rry += dy[z]
rrx += dx[z]
while matrix[bby][bbx] == '.':
bby += dy[z]
bbx += dx[z]
# 1. 구슬 B가 구멍에 빠지면 이 케이스는 더 이상 고려하지 않음
if matrix[bby][bbx] == 'O':
return [0,0,0,0]
# 2. 구슬 R이 구멍에 빠지면 구슬들이 이동한 거리 반환
elif matrix[rry][rrx] == 'O':
return [rrx-orrx, rry-orry, bbx-obbx, bby-obby]
# 3. 벽을 만난 경우
else:
# 구슬 R과 B의 위치가 동일하다면 이동 방향 기준으로 더 뒤에 있던 구슬을 한 칸 후진한다
if rrx==bbx and rry==bby:
if z==0 and orry < obby or z==1 and obby < orry:
bby -= dy[z]
elif z==0 or z==1:
rry -= dy[z]
elif z==2 and orrx < obbx or z==3 and obbx < orrx:
bbx -= dx[z]
else:
rrx -= dx[z]
# 이동한 거리 return
return [rrx-orrx-dx[z], rry-orry-dy[z], bbx-obbx-dx[z], bby-obby-dy[z]]-
처음 주어진 구슬들의 좌표를 기억하는 이유?
◽ 구슬R과B가 동일한 곳에서 멈췄을 경우 어떤 구슬을 한 칸 후진할 것인지 판단하기 위해 -
구슬
B가 구멍에 빠지면 해당 케이스는fail
⇒ 더 이상 탐색할 필요 없음을 알리기 위해[0, 0, 0, 0](이동하지 않음)반환 -
구슬
R이 구멍에 빠지면success
⇒ 구슬들의 이동거리 반환 -
구슬들이 벽을 만난 케이스
⇒ 이때 구슬들의 좌표가 동일한 경우 존재
◽ 케이스를 나눠 이동 방향 기준으로 더 뒤에 있던 구슬을 한 칸 후진시킨다
⇒ 구슬들의 이동거리 반환
.
◾ bfs를 활용하여 탐색
def bfs():
queue.append([rx, ry, bx, by, 0])
while queue:
elements = queue.popleft()
nx1 = elements[0]
ny1 = elements[1]
nx2 = elements[2]
ny2 = elements[3]
count = elements[4]
if count >= 10: return -1
for i in range(4):
z = moveTo(nx1, ny1, nx2, ny2, i)
if sum(z) != 0:
mx1 = nx1+z[0]
my1 = ny1+z[1]
mx2 = nx2+z[2]
my2 = ny2+z[3]
if matrix[my1][mx1] == 'O':
return count+1
else:
if [mx1, my1, mx2, my2] not in visited:
visited.append([mx1, my1, mx2, my2])
queue.append([mx1, my1, mx2, my2, count+1])- 큐에 구슬들의 좌표와 함께 몇 번째 움직임인지 저장하는
count변수 저장 - 한 개의 원소에 대해 상, 하, 좌, 우 이동 케이스를 검사한다
◽ 함수가[0, 0, 0, 0]을 반환한 경우 탐색 중단
◽ 반환한 값에 따라 좌표를 추적했을 때 구슬R이 구멍 위치에 있으면 그대로count+1값을 반환
◽ 이미 방문한 좌표값이 도출되었을 때는 탐색 종료
◽ 방문하지 않은 좌표일 때는 탐색 지속
.
제출 코드
from collections import deque
n, m = map(int, input().split())
rx, ry, bx, by = 0, 0, 0, 0
ru, bu = False, False
matrix = []
for i in range(n):
col = list(input())
if not ru and 'R' in col:
rx = col.index('R')
ry = i
ru = True
if not bu and 'B' in col:
bx = col.index('B')
by = i
bu = True
matrix.append(col)
matrix[ry][rx] = '.'
matrix[by][bx] = '.'
queue = deque()
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited = []
visited.append([rx, ry, bx, by])
def moveTo(rrx, rry, bbx, bby, z):
orrx, orry, obbx, obby = rrx, rry, bbx, bby
while matrix[rry][rrx] == '.':
rry += dy[z]
rrx += dx[z]
while matrix[bby][bbx] == '.':
bby += dy[z]
bbx += dx[z]
if matrix[bby][bbx] == 'O':
return [0,0,0,0]
elif matrix[rry][rrx] == 'O':
return [rrx-orrx, rry-orry, bbx-obbx, bby-obby]
else:
if rrx==bbx and rry==bby:
if z==0 and orry < obby or z==1 and obby < orry:
bby -= dy[z]
elif z==0 or z==1:
rry -= dy[z]
elif z==2 and orrx < obbx or z==3 and obbx < orrx:
bbx -= dx[z]
else:
rrx -= dx[z]
return [rrx-orrx-dx[z], rry-orry-dy[z], bbx-obbx-dx[z], bby-obby-dy[z]]
def bfs():
queue.append([rx, ry, bx, by, 0])
while queue:
elements = queue.popleft()
nx1 = elements[0]
ny1 = elements[1]
nx2 = elements[2]
ny2 = elements[3]
count = elements[4]
if count >= 10: return -1
for i in range(4):
z = moveTo(nx1, ny1, nx2, ny2, i)
if sum(z) != 0:
mx1 = nx1+z[0]
my1 = ny1+z[1]
mx2 = nx2+z[2]
my2 = ny2+z[3]
if matrix[my1][mx1] == 'O':
return count+1
else:
if [mx1, my1, mx2, my2] not in visited:
visited.append([mx1, my1, mx2, my2])
queue.append([mx1, my1, mx2, my2, count+1])
result = bfs()
if result:
print(result)
else:
print(-1)✔️ 수정 사항
-
moveTo함수에서 굳이 이동거리를 반환할 필요 없음
⇒ 좌표 반환으로 수정 -
케이스 또한 3가지로 나눌 필요 없음
⇒ 구멍에 빠지는 케이스와 그렇지 않은 케이스만으로 구분
⇒ 파란 구슬만 빠지든 빨간 구슬만 빠지든 둘 다 빠지든 이 분기에서의 탐색은 여기서 종료되기 때문에 구슬들의 좌표를 수정해줄 필요 없음 -
구슬
R과B의 좌표가 일치할 때 케이스 나누는 방식을 변경
⇒ 분명히 더 깔끔하게 나누는 방법이 있을것 같은데...! 라며 고민하다보니 조금 더 깔끔하게 변경할 수 있는 방법 발견
⇒ 이동 방향을 기준으로 더 뒤에 있었던 구슬의 좌표를 변경
⇒이동방향 * (R좌표 - B좌표)값이 음수이면 구슬R의 좌표 수정, 양수이면 구슬B의 좌표 수정
⇒(dx[z]+dy[z])*(orrx+orry-obbx-obby) -
moveTo함수의 반환값을 변경함에 따라 생기는 변경사항을bfs함수에도 적용하여 변경
수정 코드
from collections import deque
n, m = map(int, input().split())
rx, ry, bx, by = 0, 0, 0, 0
ru, bu = False, False
matrix = []
for i in range(n):
col = list(input())
if not ru and 'R' in col:
rx = col.index('R')
ry = i
ru = True
if not bu and 'B' in col:
bx = col.index('B')
by = i
bu = True
matrix.append(col)
matrix[ry][rx] = '.'
matrix[by][bx] = '.'
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited = []
visited.append([rx, ry, bx, by])
def moveTo(rrx, rry, bbx, bby, z):
orrx, orry, obbx, obby = rrx, rry, bbx, bby
while matrix[rry][rrx] == '.':
rry += dy[z]
rrx += dx[z]
while matrix[bby][bbx] == '.':
bby += dy[z]
bbx += dx[z]
if matrix[bby][bbx] == 'O' or matrix[rry][rrx] == 'O':
return [rrx, rry, bbx, bby]
else:
if rrx==bbx and rry==bby:
if (dx[z]+dy[z])*(orrx+orry-obbx-obby) > 0:
bby -= dy[z]
bbx -= dx[z]
else:
rry -= dy[z]
rrx -= dx[z]
return [rrx-dx[z], rry-dy[z], bbx-dx[z], bby-dy[z]]
def bfs():
queue = deque()
queue.append([rx, ry, bx, by, 0])
while queue:
nx1, ny1, nx2, ny2, count = queue.popleft()
if count >= 10:
return -1
for i in range(4):
z = moveTo(nx1, ny1, nx2, ny2, i)
mx1 = z[0]
my1 = z[1]
mx2 = z[2]
my2 = z[3]
if matrix[my1][mx1] == 'O' and matrix[my2][mx2] != 'O':
return count+1
else:
if [mx1, my1, mx2, my2] not in visited:
visited.append([mx1, my1, mx2, my2])
queue.append([mx1, my1, mx2, my2, count+1])
result = bfs()
print(result if result else -1)
백엔드 개발자가 되고 싶어요(22.8.15~)