[백준] 13460번 구슬 탈출 2
- 출처 : https://www.acmicpc.net/problem/13460
- 풀이 방법 : 모든 경우의 수 구하기
- 순서
- 10번의 시행 중 각 시행 당 4가지 경우의 수 구하기 (4^10) ㅠ
- 각 경우의 수 마다 성공할 경우 몇번째 시행인지 append & break
- 최솟값 출력
- 소감
- 푸는데 굉장히 오래걸렸다
- 또 pypy로 통과. 뭔가 잘못된 것 같음
- 남들은 bfs로 푼 것 같다
- 반례 검색해서 겨우겨우 실수 해결
코드
def left(board, rpos, bpos):
if rpos[1] < bpos[1]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]-1] == '#':
break
rpos[1] -= 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]-1] == '#':
break
if rpos[0] == bpos[0] and rpos[1] == bpos[1]-1:
if board[bpos[0]][bpos[1]-1] != 'O':
break
bpos[1] -= 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]-1] == '#':
break
bpos[1] -= 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]-1] == '#':
break
if rpos[0] == bpos[0] and rpos[1]-1 == bpos[1]:
if board[rpos[0]][rpos[1]-1] != 'O':
break
rpos[1] -= 1
def up(board, rpos, bpos):
if bpos[0] > rpos[0]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]-1][rpos[1]] == '#':
break
rpos[0] -= 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]-1][bpos[1]] == '#':
break
if rpos[0] == bpos[0]-1 and rpos[1] == bpos[1]:
if board[bpos[0]-1][bpos[1]] != 'O':
break
bpos[0] -= 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]-1][bpos[1]] == '#':
break
bpos[0] -= 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]-1][rpos[1]] == '#':
break
if rpos[0]-1 == bpos[0] and rpos[1] == bpos[1]:
if board[rpos[0]-1][rpos[1]] != 'O':
break
rpos[0] -= 1
def down(board, rpos, bpos):
if rpos[0] > bpos[0]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]+1][rpos[1]] == '#':
break
rpos[0] += 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]+1][bpos[1]] == '#':
break
if rpos[0] == bpos[0]+1 and rpos[1] == bpos[1]:
if board[bpos[0]+1][bpos[1]] != 'O':
break
bpos[0] += 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]+1][bpos[1]] == '#':
break
bpos[0] += 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]+1][rpos[1]] == '#':
break
if rpos[0]+1 == bpos[0] and rpos[1] == bpos[1]:
if board[rpos[0]+1][rpos[1]] != 'O':
break
rpos[0] += 1
def right(board, rpos, bpos):
if bpos[1] < rpos[1]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]+1] == '#':
break
rpos[1] += 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]+1] == '#':
break
if rpos[0] == bpos[0] and rpos[1] == bpos[1]+1:
if board[bpos[0]][bpos[1]+1] != 'O':
break
bpos[1] += 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]+1] == '#':
break
bpos[1] += 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]+1] == '#':
break
if rpos[0] == bpos[0] and rpos[1]+1 == bpos[1]:
if board[rpos[0]][rpos[1]+1] != 'O':
break
rpos[1] += 1
def recursion(idx, list_result, list_temp):
if idx == 10:
result = [t for t in list_temp]
list_result.append(result)
return
list_temp[idx] = 'l'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'r'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'u'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'd'
recursion(idx+1, list_result, list_temp)
# set board
board = []
n, m = map(int, input('').split(' '))
for i in range(n):
board.append(list(input('')))
rpos = [-1, -1]
bpos = [-1, -1]
opos = [-1, -1]
# find position
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
rpos[0] = i
rpos[1] = j
if board[i][j] == 'B':
bpos[0] = i
bpos[1] = j
if board[i][j] == 'O':
opos[0] = i
opos[1] = j
list_temp = ['' for i in range(10)]
list_result = []
recursion(0, list_result, list_temp)
list_count = []
for line in list_result:
tempr = [rpos[0], rpos[1]]
tempb = [bpos[0], bpos[1]]
for i in range(len(line)):
if line[i] == 'l':
left(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'r':
right(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'u':
up(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'd':
down(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
if len(list_count) > 0:
print(min(list_count))
else:
print(-1)
Author And Source
이 문제에 관하여([백준] 13460번 구슬 탈출 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-13460번-구슬-탈출-2
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def left(board, rpos, bpos):
if rpos[1] < bpos[1]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]-1] == '#':
break
rpos[1] -= 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]-1] == '#':
break
if rpos[0] == bpos[0] and rpos[1] == bpos[1]-1:
if board[bpos[0]][bpos[1]-1] != 'O':
break
bpos[1] -= 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]-1] == '#':
break
bpos[1] -= 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]-1] == '#':
break
if rpos[0] == bpos[0] and rpos[1]-1 == bpos[1]:
if board[rpos[0]][rpos[1]-1] != 'O':
break
rpos[1] -= 1
def up(board, rpos, bpos):
if bpos[0] > rpos[0]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]-1][rpos[1]] == '#':
break
rpos[0] -= 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]-1][bpos[1]] == '#':
break
if rpos[0] == bpos[0]-1 and rpos[1] == bpos[1]:
if board[bpos[0]-1][bpos[1]] != 'O':
break
bpos[0] -= 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]-1][bpos[1]] == '#':
break
bpos[0] -= 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]-1][rpos[1]] == '#':
break
if rpos[0]-1 == bpos[0] and rpos[1] == bpos[1]:
if board[rpos[0]-1][rpos[1]] != 'O':
break
rpos[0] -= 1
def down(board, rpos, bpos):
if rpos[0] > bpos[0]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]+1][rpos[1]] == '#':
break
rpos[0] += 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]+1][bpos[1]] == '#':
break
if rpos[0] == bpos[0]+1 and rpos[1] == bpos[1]:
if board[bpos[0]+1][bpos[1]] != 'O':
break
bpos[0] += 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]+1][bpos[1]] == '#':
break
bpos[0] += 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]+1][rpos[1]] == '#':
break
if rpos[0]+1 == bpos[0] and rpos[1] == bpos[1]:
if board[rpos[0]+1][rpos[1]] != 'O':
break
rpos[0] += 1
def right(board, rpos, bpos):
if bpos[1] < rpos[1]:
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]+1] == '#':
break
rpos[1] += 1
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]+1] == '#':
break
if rpos[0] == bpos[0] and rpos[1] == bpos[1]+1:
if board[bpos[0]][bpos[1]+1] != 'O':
break
bpos[1] += 1
else:
# move blue
while True:
if board[bpos[0]][bpos[1]] == 'O':
break
if board[bpos[0]][bpos[1]+1] == '#':
break
bpos[1] += 1
# move red
while True:
if board[rpos[0]][rpos[1]] == 'O':
break
if board[rpos[0]][rpos[1]+1] == '#':
break
if rpos[0] == bpos[0] and rpos[1]+1 == bpos[1]:
if board[rpos[0]][rpos[1]+1] != 'O':
break
rpos[1] += 1
def recursion(idx, list_result, list_temp):
if idx == 10:
result = [t for t in list_temp]
list_result.append(result)
return
list_temp[idx] = 'l'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'r'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'u'
recursion(idx+1, list_result, list_temp)
list_temp[idx] = 'd'
recursion(idx+1, list_result, list_temp)
# set board
board = []
n, m = map(int, input('').split(' '))
for i in range(n):
board.append(list(input('')))
rpos = [-1, -1]
bpos = [-1, -1]
opos = [-1, -1]
# find position
for i in range(n):
for j in range(m):
if board[i][j] == 'R':
rpos[0] = i
rpos[1] = j
if board[i][j] == 'B':
bpos[0] = i
bpos[1] = j
if board[i][j] == 'O':
opos[0] = i
opos[1] = j
list_temp = ['' for i in range(10)]
list_result = []
recursion(0, list_result, list_temp)
list_count = []
for line in list_result:
tempr = [rpos[0], rpos[1]]
tempb = [bpos[0], bpos[1]]
for i in range(len(line)):
if line[i] == 'l':
left(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'r':
right(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'u':
up(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
elif line[i] == 'd':
down(board, tempr, tempb)
if (tempr[0] == opos[0] and tempr[1] == opos[1]) and \
not (tempb[0] == opos[0] and tempb[1] == opos[1]):
list_count.append(i+1)
break
if len(list_count) > 0:
print(min(list_count))
else:
print(-1)
Author And Source
이 문제에 관하여([백준] 13460번 구슬 탈출 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-13460번-구슬-탈출-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)