BAEKJOON 13460

25 Apr 2020

문제

입력

—–

나의 처음 코드

한번에 한칸을 가는 문제들은 많이 접해봤지만, 한번에 여러칸을 가는 조건과 구멍조건, 겹칠때 조건등을 고려해야 하는 나에게 복잡한 문제였다. 처음 dfs로 풀려고 했는데, 조건의 나열 때문에 문제에 애를 먹은 상당한 시간을 보냈다. 이 문제에서는 생각해야하는게 총 3가지로, 구슬이 같은 칸에 있을 때 처리방법, 파란구슬이 먼저 들어갔을 때 처리방법, 빨간 구슬이 들어갔을 때 처리방법. 삼성 SW기출 문제라 그런지, 조건이 매우 까다로웠다. 시뮬레이션 문제 많이 풀고,,, 고수가 되어야겠다…. 갈 길이 멀다ㅠㅜ

# . 빈칸, # 벽, O 구멍, R, B

N, M = list(map(int, input().split()))
map_list = [[0] * M for _ in range(N)]
visited_list = []

#input받기
for i in range(N):
    tmp_input = input()
    for j in range(M):
        map_list[i][j] = tmp_input[j]
        if tmp_input[j] == 'R':
            map_list[i][j] = '.'
            R_coord = (i, j)
        elif tmp_input[j] == 'B':
            map_list[i][j] = '.'
            B_coord = (i, j)
#오른 아래 왼 위
rl_list = [1, 0, -1, 0]
ud_list = [0, 1, 0, -1]
g_count = 999999999

def move(r_coord, b_coord, way):
    r_count = 0
    b_count = 0
    while map_list[r_coord[0]][r_coord[1]] != '#' and map_list[r_coord[0]][r_coord[1]] != 'O':
        r_coord[0] += ud_list[way]
        r_coord[1] += rl_list[way]
        r_count += 1
    while map_list[b_coord[0]][b_coord[1]] != '#' and map_list[b_coord[0]][b_coord[1]] != 'O':
        b_coord[0] += ud_list[way]
        b_coord[1] += rl_list[way]
        b_count += 1
    #벽돌일 때는 그전 좌표로 반환을 해줘야 한다.
    if r_count >= 1 and map_list[r_coord[0]][r_coord[1]] == '#':
        r_coord[0] -= ud_list[way]
        r_coord[1] -= rl_list[way]
    if b_count >= 1 and map_list[b_coord[0]][b_coord[1]] == '#':
        b_coord[0] -= ud_list[way]
        b_coord[1] -= rl_list[way]
        
    return r_coord, r_count, b_coord, b_count


def solution(r_coord, b_coord, _count):
    global g_count
    if _count == 10:
        return
    #방문 좌표에 넣어주기
    visited_list.append((r_coord, b_coord))
    for i in range(4):
        tmp_r, r_cnt, tmp_b, b_cnt = move(list(r_coord), list(b_coord), i)
        
        #좌표의 변동이 없을 때
        if r_coord == tmp_r and b_coord == tmp_b:
            continue
        #blue가 구멍에 빠졌을 때
        if map_list[tmp_b[0]][tmp_b[1]] == 'O':
            continue
        #red가 구멍에 빠졌을 때
        if map_list[tmp_r[0]][tmp_r[1]] == 'O':
            g_count = min(g_count, _count + 1)
            continue
        #이미 방문한 좌표일 때
        if visited_list.count((tmp_r, tmp_b)) == 1:
            continue
        #둘이 좌표가 같을 때
        if tmp_r == tmp_b:
            if r_cnt > b_cnt:
                tmp_r[0] -= ud_list[i]
                tmp_r[1] -= rl_list[i]
            else:
                tmp_b[0] -= ud_list[i]
                tmp_b[1] -= rl_list[i]
                
        #이미 한번 기울여봤던 칸일 때
        if visited_list.count((tmp_r, tmp_b)) != 1:
            solution(tmp_r, tmp_b, _count + 1)
    #백트래킹 방식처럼 방문한 노드 마지막에 뺴주기        
    visited_list.pop(visited_list.index((r_coord, b_coord)))
   
        
        
solution(R_coord, B_coord, 0)
if g_count == 999999999:
    print(-1)
else:
    print(g_count)

사실 dfs로 말고, bfs로도 풀수 있다. 시뮬레이션 문제의 경우는 특히 그런것 같다. 시뮬레이션 문제라고 dfs 사고방식에 갇혀살지말자!!