아깝...! (골드 4)

#16197번 두 동전 https://www.acmicpc.net/problem/16197

16197번: 두 동전

 

열심히 코드를 짰다.

 

DFS로 도전했다가 재귀 깊이 에러가 나서 (에초에 종료조건이 없었다.)

BFS로 변경했다. (최단거리 문제는 너비우선 탐색이 좋다.)

 

틀린코드 1

r, c = map(int, input().split())
graph = []
coins = []
for i in range(r):
    row = input()
    tmp = []
    for j in range(c):
        if row[j] == "o":
            tmp.append(True)
            coins.append([i, j])
        elif row[j] == ".":
            tmp.append(True)
        else:  # row[j] == "#"
            tmp.append(False)
    graph.append(tmp)

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]


que = []


def solve(init):
    que.append(init)

    while que:
        coins = que.pop(0)
        # print(coins)
        if coins[2] > 10:
            return -1
        for i in range(4):
            # 이동
            nr1 = coins[0][0] + dr[i]
            nc1 = coins[0][1] + dc[i]
            nr2 = coins[1][0] + dr[i]
            nc2 = coins[1][1] + dc[i]
            cnt = coins[2]
            # 검증
            bool1 = 0 <= nr1 < r and 0 <= nc1 < c
            bool2 = 0 <= nr2 < r and 0 <= nc2 < c
            # print(nr1, nc1, bool1, nr2, nc2, bool2)
            # 이동한 위치가 벽일 경우에 보정
            if bool1 and not graph[nr1][nc1]:
                nr1, nc1 = coins[0][0], coins[0][1]
            if bool2 and not graph[nr2][nc2]:
                nr2, nc2 = coins[1][0], coins[1][1]

            if bool1 and bool2:  # 둘 다 안떨어졌을 때
                que.append([[nr1, nc1], [nr2, nc2], cnt+1])
            elif not bool1 and not bool2:  # 둘 다 떨어졌을 때
                continue
            else:  # 하나만 떨어졌을 때
                return cnt+1
            # exit()


print(solve(coins+[0]))

버튼을 누른 횟수가 10이 넘어가면 종료하도록 했는데

문제는 10이 넘어갈 때까지 연산 횟수가 너무 많다는 점이다.

 

그래서 방문 기록을 해야겠다는 생각을 했다.

근데 문제는 동전이 두개라는 점이다.

 

틀린코드 2

 

r, c = map(int, input().split())
graph = []
coins = []
for i in range(r):
    row = input()
    tmp = []
    for j in range(c):
        if row[j] == "o":
            tmp.append(True)
            coins.append([i, j])
        elif row[j] == ".":
            tmp.append(True)
        else:  # row[j] == "#"
            tmp.append(False)
    graph.append(tmp)

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
visited = [[[[False]*c for _ in range(r)]
            for __ in range(c)] for ___ in range(r)]

que = []


def solve(init):
    que.append(init)
    visited[init[0][0]][init[0][1]][init[1][0]][init[1][1]] = True
    while que:
        coins = que.pop(0)
        # print(coins)
        if coins[2] > 10:
            return -1
        for i in range(4):
            # 이동
            nr1 = coins[0][0] + dr[i]
            nc1 = coins[0][1] + dc[i]
            nr2 = coins[1][0] + dr[i]
            nc2 = coins[1][1] + dc[i]
            cnt = coins[2]
            # 검증
            bool1 = 0 <= nr1 < r and 0 <= nc1 < c
            bool2 = 0 <= nr2 < r and 0 <= nc2 < c
            # print(nr1, nc1, bool1, nr2, nc2, bool2)
            # 이동한 위치가 벽일 경우에 보정
            if bool1 and not graph[nr1][nc1]:
                nr1, nc1 = coins[0][0], coins[0][1]
            if bool2 and not graph[nr2][nc2]:
                nr2, nc2 = coins[1][0], coins[1][1]

            if bool1 and bool2:  # 둘 다 안떨어졌을 때
                if not visited[nr1][nc1][nr2][nc2]:
                    visited[nr1][nc1][nr2][nc2] = True
                    que.append([[nr1, nc1], [nr2, nc2], cnt+1])
            elif not bool1 and not bool2:  # 둘 다 떨어졌을 때
                continue
            else:  # 하나만 떨어졌을 때
                return cnt+1
            # exit()
    return -1


print(solve(coins+[0]))

그렇게 수정한 코드이다. 2개의 동전이 특정 위치에 각각 존재했던 경우를 기록한다고 보면 된다. (4차원 리스트)

 

근데 틀렸다. (왜..?)

 

정확한 이유는 짚기 어렵지만

논리 순서가 잘못됐다고 판단했다.

 

1. 둘 다 떨어졌을 때 ( 두개의 코인이 모두 그래프의 범위를 벗어날 때)

2. 하나만 떨어졌을 때 (문제가 요구하는 상황)

3. 벽을 만났을 때

4. 둘 다 안떨어졌을 때

 

정답코드

 

r, c = map(int, input().split())
graph = []
coins = []
for i in range(r):
    row = input()
    tmp = []
    for j in range(c):
        if row[j] == "o":
            tmp.append(True)
            coins.append([i, j])
        elif row[j] == ".":
            tmp.append(True)
        else:  # row[j] == "#"
            tmp.append(False)
    graph.append(tmp)

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
visited = [[[[False]*c for _ in range(r)]
            for __ in range(c)] for ___ in range(r)]

que = []


def visitable(x, y):
    return 0 <= x < r and 0 <= y < c


def solve(init):
    que.append(init)
    visited[init[0][0]][init[0][1]][init[1][0]][init[1][1]] = True
    while que:
        coins = que.pop(0)
        # print(coins)
        if coins[2] > 10:
            break
        for i in range(4):
            # 이동
            nr1 = coins[0][0] + dr[i]
            nc1 = coins[0][1] + dc[i]
            nr2 = coins[1][0] + dr[i]
            nc2 = coins[1][1] + dc[i]
            cnt = coins[2]
            # 둘 다 떨어졌을 때
            if not visitable(nr1, nc1) and not visitable(nr2, nc2):
                continue
            # 하나만 떨어졌을 때
            if (not visitable(nr1, nc1) and visitable(nr2, nc2)) or (visitable(nr1, nc1) and not visitable(nr2, nc2)):
                return cnt
            # 벽을 만났을 때
            if not graph[nr1][nc1]:
                nr1, nc1 = coins[0][0], coins[0][1]
            if not graph[nr2][nc2]:
                nr2, nc2 = coins[1][0], coins[1][1]
            # 둘 다 안떨어졌을 때
            if not visited[nr1][nc1][nr2][nc2]:
                visited[nr1][nc1][nr2][nc2] = True
                que.append([[nr1, nc1], [nr2, nc2], cnt+1])
    return -1


print(solve(coins+[1]))

 

탈락되는 경우의 수가 가장 많은 경우를 우선으로 진행하는게 맞다고 느꼈다.

게다가, 둘 다 떨어진 경우는 그래프의 범위를 벗어나는 경우이다. 즉 틀린코드처럼 벽을 만나는 경우를 우선 처리할 경우에 index error를 고려한 코드를 추가로 작성해야한다. 

-> 논리적 구조가 복잡해진다.

 

깨달은 바가 있는 문제였다.