문제 링크
문제 코드
from collections import deque
import copy
num_list = list(map(int, input().split()))
row=num_list[0]
col= num_list[1]
maze = [[0 for r in range(col)]for c in range(row)]
visited =[]
for i in range(row):
maze_list = input()
#maze_list = f.readline()
for j in range(col):
maze[i][j] = maze_list[j]
if maze[i][j] == 'B':
blue= [i,j]
if maze[i][j] == 'R':
red= [i,j]
if maze[i][j] == 'O':
hole = [i,j]
def print_maze(maze):
for i in maze:
print(i)
que = deque()
que.append([red,blue,0,maze])
# up,down,left,right
dx = [-1,1,0,0]
dy = [0,0,-1,1]
max_count = -1
while_breaker = False
visited.append(maze)
while len(que)>0:
tmp = que.popleft()
now_red = tmp[0]
now_blue = tmp[1]
count = tmp[2]
if max_count != -1:
break
if count >= 10:
break
for i in range(4):
tmp_maze = copy.deepcopy(tmp[3])
red_x, red_y = now_red
blue_x, blue_y = now_blue
next_red_x = red_x + dx[i]
next_red_y = red_y + dy[i]
next_blue_x = blue_x + dx[i]
next_blue_y = blue_y + dy[i]
start_red = [now_red[0],now_red[1]]
start_blue = [now_blue[0],now_blue[1]]
if 0 <= next_red_x < row and 0 <= next_red_y < col:
while tmp_maze[next_red_x][next_red_y] != '#' and tmp_maze[next_blue_x][next_blue_y] != '#': #먼저 동시에 굴려서 벽에 닿는 구슬이 있을때까지
if tmp_maze[next_red_x][next_red_y] == 'O': # 레드 구슬이 다음번에 구멍에 닿으면
tmp_maze[red_x][red_y] = '.' #우선 레드가 없다고 생각해보기
tmp_blue_x = next_blue_x
tmp_blue_y = next_blue_y
while tmp_maze[tmp_blue_x][tmp_blue_y] == '.': # 레드가 없을때 동시에 블루 구슬도 들어가는지 확인해보기
tmp_blue_x += dx[i]
tmp_blue_y += dy[i]
if tmp_maze[tmp_blue_x][tmp_blue_y] == 'O': #구멍에 들어간다면 동시 입력이 되서 종료
while_breaker = True
break
if count + 1 > max_count: #블루 구슬이 구멍에 들어가지 않는다면, 레드 구슬이 잘 들어간거임
max_count = count + 1
if tmp_maze[next_blue_x][next_blue_y] == 'O': #블루 구슬이 먼저 구멍에 들어간다면 종료
while_breaker = True
break
#visited[next_red_x][next_red_y] = 1
tmp_maze[red_x][red_y] = '.'
tmp_maze[blue_x][blue_y] = '.'
tmp_maze[next_red_x][next_red_y] = 'R'
tmp_maze[next_blue_x][next_blue_y] = 'B'
red_x = next_red_x
red_y = next_red_y
blue_x = next_blue_x
blue_y = next_blue_y
next_red_x = red_x + dx[i]
next_red_y = red_y + dy[i]
next_blue_x = blue_x + dx[i]
next_blue_y = blue_y + dy[i]
while while_breaker == False and(tmp_maze[next_red_x][next_red_y] == '.' or tmp_maze[next_red_x][next_red_y] == 'O'): #블루가 먼저 벽에 닿으면 레드를 나머지 굴려줌
if tmp_maze[next_red_x][next_red_y] == 'O': # 레드 구슬이 다음번에 구멍에 닿으면
tmp_maze[red_x][red_y] = '.' #우선 레드가 없다고 생각해보기
tmp_blue_x = next_blue_x
tmp_blue_y = next_blue_y
while tmp_maze[tmp_blue_x][tmp_blue_y] == '.': # 레드가 없을때 동시에 블루 구슬도 들어가는지 확인해보기
tmp_blue_x += dx[i]
tmp_blue_y += dy[i]
if tmp_maze[tmp_blue_x][tmp_blue_y] == 'O': # 구멍에 들어간다면 동시 입력이 되서 종료
while_breaker = True
break
if count + 1 > max_count: #블루 구슬이 구멍에 들어가지 않는다면, 레드 구슬이 잘 들어간거임
max_count = count + 1
tmp_maze[red_x][red_y] = '.'
tmp_maze[next_red_x][next_red_y] = 'R'
red_x = next_red_x
red_y = next_red_y
next_red_x = red_x + dx[i]
next_red_y = red_y + dy[i]
while while_breaker == False and (tmp_maze[next_blue_x][next_blue_y] == '.' or tmp_maze[next_blue_x][next_blue_y] == 'O'): # 레드가 먼저 벽에 닿으면 블루를 나머지 굴려줌
if tmp_maze[next_blue_x][next_blue_y] == 'O': #블루 구슬이 먼저 구멍에 들어간다면 종료
while_breaker = True
#max_count = -1
break
tmp_maze[blue_x][blue_y] = '.'
tmp_maze[next_blue_x][next_blue_y] = 'B'
blue_x = next_blue_x
blue_y = next_blue_y
next_blue_x = blue_x + dx[i]
next_blue_y = blue_y + dy[i]
if while_breaker == False and (tmp_maze[next_red_x][next_red_y] == '#' or tmp_maze[next_red_x][next_red_y]== 'B'):
if tmp_maze not in visited:
visited.append(tmp_maze)
que.append([[next_red_x-dx[i],next_red_y-dy[i]],[next_blue_x-dx[i],next_blue_y-dy[i]],count+1,tmp_maze])
print(max_count)
문제 풀이
- 첫번째 시도
- 다음번 레드 구슬이 갈곳이 '.'이면 이동하도록함
- 레드의 이동이 끝나고 블루가 이동하도록 함
- 블루가 이동하다가 구멍을 만나면 종료하도록 함
- 레드의 다음번 가야할곳이 '#'이면 큐에다가 다음번 가야할 곳을 넣음
- 레드의 다음번 가야할곳이 'O'이면 red의 현재위치를 빈곳으로 만들고 블루가 이동하면서 구멍을 만나면 마찬가지로 -1을 출력하고 종료하도록 함
- 블루가 구멍을 만나지 않는다면 레드가 무사히 구멍을 통과한 것으로 생각하고 count 세서 종료
- 그리고 끝났을때 red의 위치와 블루의 위치가 겹치면 -1 출력하도록 함
- 두번째 시도
- 첫번째 시도와 같은데, red의 위치와 블루의 위치가 겹치는 경우가 없을 것이라고 생각해서 해당 부분을 지움
- 세번째 시도
- 디버깅을 해보니 왔던길을 다시가는 경우가 생기는 것 같아 visited를 추가함
- 레드 앞에 바로 블루가 있는 경우에도 추가적인 이동이 있을 수 있어서 큐에 추가하도록 함 (해당 케이스는 밑의 반례에서 나올예정)
- 네번째 시도
- tmp_maze 변수를 만들어서 que에서 들고가도록 함
- maze를 deepcopy 함
- tmp_maze에서는 실제 움직이는 방향으로 R과 B를 새롭게 그려넣어줌
- 다섯번째 시도
- 블루가 구멍을 만나는 경우 while breaker를 통해서 빠져나가도록 했는데, BFS의 특성상 먼저 구멍을 만나더라도 다른 케이스에서 잘 나가는 경우가 있음을 발견함, 따라서 while breaker를 disable함
- 잘 나온 케이스 즉 레드만 구멍에 빠지고 블루는 안빠지는 경우를 찾아내서 max count를 갱신할 경우, 나머지 queue에 있는 내용들은 계산 안하고 빠지도록 분기문을 만들어줌
- 여섯번째 시도
- 레드가 벽을 마주치면 안가도록 처음에 생각했었는데 반례 케이스를 보니 벽이 있더라도 블루가 움직이면서 다음번에 기회가 생기는 경우가 발생
- 레드의 다음 위치가 무엇이더라도 모든 방향으로 이동해보도록 함
- 단 처음의 레드의 위치와 블루의 위치가 변하지 않는 경우는 프루닝함
- 큐에 넣을때 현재의 보드의 모양을 visited에 기록해둠, visited에 있는 보드 모양이면 큐에 넣지 않음
- 진행중 블루가 먼저 구멍에 닿으면 해당 케이스는 폐기할 수 있도록 while_breaker를 걸어둠
- while_breaker의 and와 or가 잘못 연결되어서 에러가 남(주의할 것)
추가 예시
10 10
##########
#R#...##B#
#...#..###
######.#.#
#......#.#
#.######.#
#.#....#.#
#.######.#
#..O#.##.#
##########
answer : 10
10 10
##########
#R#...##B#
#...#..###
######.#.#
#......#.#
#.######.#
#.#....#.#
#.#O####.#
#...#.##.#
##########
answer : -1
움직이는 횟수가 10이 넘는 경우
5 5
##### ##O## #RB.# ##### #####answer : 2
가는 방향에 B가 있더라도 움직이는 경우
6 7
#######
#R....#
#.....#
#..O..#
#..B..#
#######
answer : 3
B가 먼저 구멍에 들어가더라도 종료를 하면 안되는 경우
7 10
##########
#.......O#
###.#.#.##
#........#
#B#.###..#
#R...#...#
##########
answer : 6
R이 벽방향이더라도 B를 움직여봐야함
개발하는 멍멍이