[구현] 백준 13460번 구슬 탈출2

이번 문제는 구현문제 입니다. 

문제 출처: https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

---

처음 작성한 코드는 274 line 정도였습니다...ㅎㅎ

 

처음 작성 코드

import collections

answer = -1
num_row, num_col = map(int, input().split())
info = []
pos_r = (-1, -1)
pos_b = (-1, -1)

# input
for r in range(num_row):
    info.append(list(input()))

for r in range(num_row):
    for c in range(num_col):
        if info[r][c] == 'R':
            info[r][c] = '.'
            pos_r = (r, c)
        elif info[r][c] == 'B':
            info[r][c] = '.'
            pos_b = (r, c)


def go_up(cur_r, cur_b, visit, q):
    # 빨간공이 파란공 밑에 있을 때 -> 파란공 먼저 이동
    new_r = cur_r
    new_b = cur_b
    if cur_r[0] >= cur_b[0]:
        for r in range(cur_b[0] - 1, 0, -1):
            if info[r][cur_b[1]] == '.':
                new_b = (r, cur_b[1])
            elif info[r][cur_b[1]] == 'O':
                return False
            elif info[r][cur_b[1]] == '#':
                break

        for r in range(cur_r[0] - 1, 0, -1):
            if r == new_b[0] and cur_r[1] == new_b[1]:
                break
            elif info[r][cur_r[1]] == '.':
                new_r = (r, cur_r[1])
            elif info[r][cur_r[1]] == 'O':
                return True
            elif info[r][cur_r[1]] == '#':
                break

    else: # 빨간공 먼저 이동
        for r in range(cur_r[0] - 1, 0, -1):
            if info[r][cur_r[1]] == '.':
                new_r = (r, cur_r[1])
            elif info[r][cur_r[1]] == 'O':
                # 파란공 빠지는지 확인해야함
                flag = True
                if cur_r[1] == cur_b[1]:
                    flag = False
                    for r_b in range(cur_b[0] - 1, r, -1):
                        if info[r_b][cur_b[1]] == '#':
                            flag = True
                            break
                if flag:
                    return True
                else:
                    return False

            elif info[r][cur_r[1]] == '#':
                break

        for r in range(cur_b[0] - 1, 0, -1):
            if r == new_r[0] and cur_b[1] == new_r[1]:
                break
            elif info[r][cur_b[1]] == '.':
                new_b = (r, cur_b[1])
            elif info[r][cur_b[1]] == 'O':
                return False
            elif info[r][cur_b[1]] == '#':
                break


    if not visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]]:
        visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]] = True
        q.append((new_r[0], new_r[1], new_b[0], new_b[1]))


def go_down(cur_r, cur_b, visit, q):
    new_r = cur_r
    new_b = cur_b
    # 빨간공이 밑에 있을 때 -> 빨간공 먼저 움직임
    if cur_r[0] >= cur_b[0]:
        for row_red in range(cur_r[0] + 1, num_row):
            if info[row_red][cur_r[1]] == '.':
                new_r = (row_red, cur_r[1])
            elif info[row_red][cur_r[1]] == 'O':
                # 파란공이 빠지는지 확인
                flag = True
                if cur_b[1] == cur_r[1]:
                    flag = False
                    for row_blue in range(cur_b[0] + 1, row_red):
                        if info[row_blue][cur_b[1]] == '#':
                            flag = True
                            break
                if flag:
                    return True
                else:
                    return False
            elif info[row_red][cur_r[1]] == '#':
                break

        for row_blue in range(cur_b[0] + 1, num_row):
            if row_blue == new_r[0] and cur_b[1] == new_r[1]:
                break
            elif info[row_blue][cur_b[1]] == '.':
                new_b = (row_blue, cur_b[1])
            elif info[row_blue][cur_b[1]] == 'O':
                return False
            elif info[row_blue][cur_b[1]] == '#':
                break
    else:
        for row_blue in range(cur_b[0] + 1, num_row):
            if info[row_blue][cur_b[1]] == '.':
                new_b = (row_blue, cur_b[1])
            elif info[row_blue][cur_b[1]] == 'O':
                return False
            elif info[row_blue][cur_b[1]] == '#':
                break

        for row_red in range(cur_r[0] + 1, num_row):
            if row_red == new_b[0] and cur_r[1] == new_b[1]:
                break
            elif info[row_red][cur_r[1]] == '.':
                new_r = (row_red, cur_r[1])
            elif info[row_red][cur_r[1]] == 'O':
                return True
            elif info[row_red][cur_r[1]] == '#':
                break

    if not visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]]:
        visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]] = True
        q.append((new_r[0], new_r[1], new_b[0], new_b[1]))


def go_left(cur_r, cur_b, visit, q):
    # 파란공이 빨간공 왼쪽에 있을 때 -> 파란공 먼저 이동
    new_r = cur_r
    new_b = cur_b
    if cur_b[1] <= cur_r[1]:
        for col_blue in range(cur_b[1] - 1, 0, -1):
            if info[cur_b[0]][col_blue] == '.':
                new_b = (cur_b[0], col_blue)
            elif info[cur_b[0]][col_blue] == 'O':
                return
            elif info[cur_b[0]][col_blue] == '#':
                break

        for col_red in range(cur_r[1] - 1, 0, -1):
            if cur_r[0] == new_b[0] and col_red == new_b[1]:
                break
            elif info[cur_r[0]][col_red] == '.':
                new_r = (cur_r[0], col_red)
            elif info[cur_r[0]][col_red] == 'O':
                return True
            elif info[cur_r[0]][col_red] == '#':
                break

    else: # 빨간공 먼저 이동
        for col_red in range(cur_r[1] - 1, 0, -1):
            if info[cur_r[0]][col_red] == '.':
                new_r = (cur_r[0], col_red)
            elif info[cur_r[0]][col_red] == 'O':
                # 파란공 빠지는지 확인해야함
                flag = True
                if cur_r[0] == cur_b[0]:
                    flag = False
                    if '#' in info[cur_b[0]][col_red : cur_b[1]]:
                        flag = True
                if flag:
                    return True
                else:
                    return False
            elif info[cur_r[0]][col_red] == '#':
                break

        for col_blue in range(cur_b[1] - 1, 0, -1):
            if cur_b[0] == new_r[0] and col_blue == new_r[1]:
                break
            elif info[cur_b[0]][col_blue] == '.':
                new_b = (cur_b[0], col_blue)
            elif info[cur_b[0]][col_blue] == 'O':
                return False
            elif info[cur_b[0]][col_blue] == '#':
                break

    if not visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]]:
        visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]] = True
        q.append((new_r[0], new_r[1], new_b[0], new_b[1]))


def go_right(cur_r, cur_b, visit, q):
    # 파란공이 빨간공 오른쪽에 있을 때 -> 파란공 먼저 이동
    new_r = cur_r
    new_b = cur_b
    if cur_b[1] >= cur_r[1]:
        for col_blue in range(cur_b[1] + 1, num_col):
            if info[cur_b[0]][col_blue] == '.':
                new_b = (cur_b[0], col_blue)
            elif info[cur_b[0]][col_blue] == 'O':
                return
            elif info[cur_b[0]][col_blue] == '#':
                break

        for col_red in range(cur_r[1] + 1, num_col):
            if cur_r[0] == new_b[0] and col_red == new_b[1]:
                break
            elif info[cur_r[0]][col_red] == '.':
                new_r = (cur_r[0], col_red)
            elif info[cur_r[0]][col_red] == 'O':
                return True
            elif info[cur_r[0]][col_red] == '#':
                break

    else: # 빨간공 먼저 이동
        for col_red in range(cur_r[1] + 1, num_col):
            if info[cur_r[0]][col_red] == '.':
                new_r = (cur_r[0], col_red)
            elif info[cur_r[0]][col_red] == 'O':
                # 파란공 빠지는지 확인해야함
                flag = True
                if cur_r[0] == cur_b[0]:
                    flag = False
                    if '#' in info[cur_b[0]][cur_b[1] : col_red]:
                        flag = True
                if flag:
                    return True
                else:
                    return False
            elif info[cur_r[0]][col_red] == '#':
                break

        for col_blue in range(cur_b[1] + 1, num_col):
            if cur_b[0] == new_r[0] and col_blue == new_r[1]:
                break
            elif info[cur_b[0]][col_blue] == '.':
                new_b = (cur_b[0], col_blue)
            elif info[cur_b[0]][col_blue] == 'O':
                return False
            elif info[cur_b[0]][col_blue] == '#':
                break

    if not visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]]:
        visit[new_r[0]][new_r[1]][new_b[0]][new_b[1]] = True
        q.append((new_r[0], new_r[1], new_b[0], new_b[1]))


q = collections.deque()
visit = [[[[False] * num_col for _ in range(num_row)] for _ in range(num_col)] for _ in range(num_row)]
cur = (pos_r[0], pos_r[1], pos_b[0], pos_b[1])
q.append(cur)
visit[pos_r[0]][pos_r[1]][pos_b[0]][pos_b[1]] = True
cnt = 0

while len(q) > 0 and answer == -1 and cnt < 10:
    q_size = len(q)
    cnt += 1

    for _ in range(q_size):
        cur = q.popleft()
        cur_r = (cur[0], cur[1])
        cur_b = (cur[2], cur[3])

        if go_up(cur_r, cur_b, visit, q) or go_down(cur_r, cur_b, visit, q) or \
                go_right(cur_r, cur_b, visit, q) or go_left(cur_r, cur_b, visit, q):
            answer = cnt

print(answer)

모든 케이스들을 각각 구현한 코드입니다.

공통적으로 뽑아낼 수 있는 부분이 있었음에도 불구하고,

모든 케이스들을 구구절절 코딩하려다 보니 길이가 길어졌습니다.

 

다른 풀이들을 참고하여 새로 작성한 코드는 아래와 같습니다.

import collections

answer = -1
drs = [-1, 1, 0, 0]
dcs = [0, 0, -1, 1]
num_row, num_col = map(int, input().split())
info = []
for row in range(num_row):
    info.append(list(input()))

pos_red = (-1, -1)
pos_blue = (-1, -1)
for row in range(num_row):
    for col in range(num_col):
        if info[row][col] == 'R':
            pos_red = (row, col)
            info[row][col] = '.'
        elif info[row][col] == 'B':
            pos_blue = (row, col)
            info[row][col] = '.'


def move(dr, dc, cur):
    # return: new_pos, distance
    new_row = cur[0]
    new_col = cur[1]
    distance = 0
    while True:
        if info[new_row][new_col] == 'O' or info[new_row + dr][new_col + dc] == '#':
            return (new_row, new_col), distance
        new_row += dr
        new_col += dc
        distance += 1


def solution():
    q = collections.deque()
    visit = [[[[False] * num_col for _ in range(num_row)] for _ in range(num_col)] for _ in range(num_row)]
    visit[pos_red[0]][pos_red[1]][pos_blue[0]][pos_blue[1]] = True
    q.append((pos_red, pos_blue))
    cnt = 0

    while len(q) > 0 and cnt < 10:
        q_size = len(q)
        cnt += 1

        for _ in range(q_size):
            cur_red, cur_blue = q.popleft()
            for i in range(4):
                dr = drs[i]
                dc = dcs[i]

                new_red, distance_red = move(dr, dc, cur_red)
                new_blue, distance_blue = move(dr, dc, cur_blue)

                if info[new_red[0]][new_red[1]] == 'O':
                    if info[new_blue[0]][new_blue[1]] == 'O':
                        continue
                    else:
                        print(cnt)
                        return
                elif new_red == new_blue:
                    if distance_red > distance_blue:
                        new_red = (new_red[0] - dr, new_red[1] - dc)
                    else:
                        new_blue = (new_blue[0] - dr, new_blue[1] - dc)

                if not visit[new_red[0]][new_red[1]][new_blue[0]][new_blue[1]]:
                    visit[new_red[0]][new_red[1]][new_blue[0]][new_blue[1]] = True
                    q.append((new_red, new_blue))

    print(-1)
    return


solution()

 

처음 작성 코드에서의 go_up, go_down, go_right, go_left를 move라는 하나의 function으로 묶었습니다.

또한 파란공과 빨간공이 겹쳐지는 경우를 두번째 코드에서 훨씬 더 간단한 방법으로 고려해줬습니다.