백준) 구슬탈출 - 실패

백준) 구슬탈출

 

이번 포스팅은 하지 않을 생각이였다. 이유는 내가 답을 찾지 못한 문제여서이다. 그러나 미래의 나를 위하여 문제 접근 방식부터 코드의 각 부분을 해석 한 글을 작성하기로 생각하였다.

 

1. 문제
   • 구슬 2개(빨강, 파랑) 중 빨강 구슬을 N * M 배열에 출구 'O'에 도달할 수 있으면 1을 아니면 0을 출력
   • 이때 빠져나오는 구슬은 빨강 하나여야 한다
   • 또한 도전 기회는 10회 이며 10회를 초과 하면 탈출 실패로 간주 하여 0을 출력
   • 기울기는 상하좌우만 되며 기울어졌을 때 모든 구슬이 해당 방향으로 이동
   • 구슬은 겹쳐지 않는다
2. 문제 풀이
   • 먼저 N과 M을 입력 받는 부분 작성
   • 이후 N * M의 배열의 값들을 입력 받아 저장하는 부분 작성
   • 입력받아 저장하는 부분에서 구슬들의 초기 위치를 저장 기록
   • BFS 방식으로 모든 경우의 수를 앞에서 부터 찾기 시작
   • 이후 내용은 코드의 주석에 달아 놓겠다

실패 코드

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
maps = []
R = []
B = []
for i in range(N):
    map_add = list(map(str, sys.stdin.readline().strip()))
    maps.append(map_add)
    if 'R' in map_add or 'B' in map_add:
        for j, word in enumerate(map_add):
            if word == 'R':
                R = [i, j]
            if word == 'B':
                B = [i, j]

# 구슬의 이동 
def moves(x, y, dx, dy, gole_check):
    nx, ny = x, y
    i = 1
    while True:
        cnx, cny = x + (i * dx), y + (i * dy)
        # 구슬이 맵에서 벗어 나는지와 벽또는 앞의 구슬에 막혔는지 확인
        if cnx < 0 or cnx >= N or cny < 0 or cny >= M:
            break
        elif maps[cnx][cny] in ['#', 'R', 'B']:
            break
        else:
            nx, ny = cnx, cny
            # 구슬이 출구를 통과 했는지 확인
            if maps[nx][ny] == 'O':
                if maps[x][y] == 'R':
                    gole_check[0] = True
                else:
                    gole_check[1] = True
        i += 1

    return nx, ny, gole_check


def bfs(R, B):
	# 구슬이 출구에 도달 했는 확인 하는 함수
    is_gols = [False, False]
    dq = deque([0, R, B])
    
    # 구슬의 초기 위치 기록
    x1, y1 = R
    x2, y2 = B
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while dq:
        count = dq.popleft()
        # 기울기의 획수가 10이상면 실패로 종료
        if count > 10:
        	is_gols = [False, False]
            return
        
        # 구슬이 이동하기에 맵에 그려진 구슬을 일단 자리 비움
        maps[x1][y1] = '.'
        maps[x2][y2] = '.'
        rx, ry = dq.popleft()
        bx, by = dq.popleft()
        # 구슬이 받아 변수 값 부터 이동 하기에 초기 위기 셋팅
        maps[rx][ry] = 'R'
        maps[bx][by] = 'B'

        # if count == 6:
        #     print(count)
        #     print('\n'.join(map(str, maps)))
        for i in range(4):
            # 구슬이 출구로 나가지 않은 상태로 가정하기 구슬의 상태 초기화
            is_gols = [False, False]
            
            # 어떤 구슬부터 움직일지 확인
            if (i == 0 and rx < bx) or (i == 1 and rx > bx) or (i == 2 and ry < by) or (i == 3 and ry > by):
                nrx, nry, is_gols = moves(rx, ry, dx[i], dy[i], is_gols)
                
                # 구슬이 동일 한 위치 이면 일단 먼저 해당 구슬 위치 이동
                if ry == by or rx == bx:
                    maps[rx][ry], maps[nrx][nry] = maps[nrx][nry], maps[rx][ry]
                nbx, nby, is_gols = moves(bx, by, dx[i], dy[i], is_gols)
                
                # 이동 해두었던 위치 초기화
                if ry == by or rx == bx:
                    maps[rx][ry], maps[nrx][nry] = maps[nrx][nry], maps[rx][ry]
                if is_gols[1]: continue
            else:
                nbx, nby, is_gols = moves(bx, by, dx[i], dy[i], is_gols)
                if is_gols[1]: continue
                
                # 구슬이 동일 한 위치 이면 일단 먼저 해당 구슬 위치 이동
                if ry == by or rx == bx:
                    maps[bx][by], maps[nbx][nby] = maps[nbx][nby], maps[bx][by]
                nrx, nry, is_gols = moves(rx, ry, dx[i], dy[i], is_gols)
                
                # 이동 해두었던 위치 초기화
                if ry == by or rx == bx:
                    maps[bx][by], maps[nbx][nby] = maps[nbx][nby], maps[bx][by]

			# 빨강 구슬만 출구를 이동했다면 함수 종료
            if is_gols == [True, False]:
                return is_gols

			# 파랑 구슬이 출구를 밟았다면 이후 검색은 필요없기에 다음 작업 수행
            if is_gols[1]:
                continue
			
            # 구슬이 이동이 되었다면 큐에 기록
            if rx != nrx or ry != nry or bx != nbx or by != nby:
                dq.append(count + 1)
                dq.append([nrx, nry])
                dq.append([nbx, nby])

        # 기존의 위치를 초기화 한 뒤 최초의 상태로 구슬 위치 변경
        maps[rx][ry] = '.'
        maps[bx][by] = '.'

        maps[x1][y1] = 'R'
        maps[x2][y2] = 'B'
    return is_gols


check = bfs(R, B)
if check == [True, False]:
    sys.stdout.write(f'{1}')
else:
    sys.stdout.write(f'{0}')

 

 

이 문제는 스쿼드방에서 코드리뷰를 진행한다고 하여 일단 실패 한 상태로 둔 후 코드리뷰 후 다시 코드를 작성 하여 통과 해볼 생각이다.

지금으로써는 어디서, 왜 틀렸는지 조차도 이해가 안되는 상황이라 더는 붙잡고 풀 수는 없을거 같다..