백준 17070번: 파이프 옮기기 1 (파이썬, DFS, DP)

멘탈이 나간 문제이다. 골드V에서 이정도로 헤멘건 처음이다..

 

삼성 A형 기출문제중 하나인데 2차원 배열이 주어지길래 당연히 dfs, bfs로 접근하려 했다. 나는 bfs로 접근하였는데 

 

파이프가 가로인지, 세로인지, 대각선인지 판단을 해야해서 queue에 두 점의 좌표를 튜플과 리스트로 감싸 넣었다.

 

대각선일땐 세점이 방문 불가하고 파이프의 왼쪽은 파이프가 옮겨질 때 옮겨지기 전 파이프 오른쪽의 좌표로 옮겨진다는 두 포인트를 잡고 코드를 짰다.

 

import sys
from collections import deque


def bfs(n):
    global cnt
    queue = deque(n)
    while queue:
        now = queue.popleft()
        if now[0][0] - now[1][0] == 0:  # 행이 같으므로 가로 배치, →, ↘ 가능
            for idx, i in enumerate([[(0, 1), (0,1)], [(0,1), (1, 1)]]):
                cash = [(now[0][0]+i[0][0], now[0][1]+i[0][1]), (now[1][0]+i[1][0], now[1][1]+i[1][1])]
                if idx == 0:
                    if N > cash[1][0] >= 0 and 1 <= cash[1][1] < N and graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
                else:
                    if 0 <= cash[1][0] < N and 0 <= cash[1][0]-1 < N and 0 <= cash[1][1] < N and N > cash[1][
                        1] - 1 >= 0 == graph[cash[1][0] - 1][cash[1][1]] and graph[cash[1][0]][cash[1][1] - 1] == 0 and \
                            graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
        elif now[0][1] - now[1][1] == 0:
            for idx, i in enumerate([[(1, 0),(1,0)], [(1,0), (1, 1)]]):
                cash = [(now[0][0] + i[0][0], now[0][1] + i[0][1]), (now[1][0] + i[1][0], now[1][1] + i[1][1])]
                if idx == 0:
                    if N > cash[1][0] >= 0 and 1 <= cash[1][1] < N and graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
                else:
                    if 0 <= cash[1][0] < N and 0 <= cash[1][0]-1 < N and 0 <= cash[1][1] < N and N > cash[1][
                        1] - 1 >= 0 == graph[cash[1][0] - 1][cash[1][1]] and graph[cash[1][0]][cash[1][1] - 1] == 0 and \
                            graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
        else:
            for idx, i in enumerate([[(1,1),(0,1)], [(1,1), (1,0)], [(1,1),(1,1)]]):
                cash = [(now[0][0] + i[0][0], now[0][1] + i[0][1]), (now[1][0] + i[1][0], now[1][1] + i[1][1])]
                if idx == 2:
                    if 0 <= cash[1][0] < N and 0 <= cash[1][0] - 1 < N and 0 <= cash[1][1] < N and N > cash[1][
                        1] - 1 >= 0 == graph[cash[1][0] - 1][cash[1][1]] and graph[cash[1][0]][cash[1][1] - 1] == 0 and \
                            graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
                else:
                    if N > cash[1][0] >= 0 and 1 <= cash[1][1] < N and graph[cash[1][0]][cash[1][1]] == 0:
                        queue.append(cash)
        if now[1][0] == N-1 and now[1][1] == N-1:
            cnt += 1


start = [[(0,0),(0,1)]]
N = int(sys.stdin.readline())
graph = []
for __ in range(N):
    graph.append(list(map(int, sys.stdin.readline().strip().split())))

cnt = 0
bfs(start)
print(cnt)

보기 좋게 시간초과가 났다. 도저히 감이 안왔던 나는 다른 분들의 풀이를 참고했고 dfs, bfs로는 풀 수 없고 dp로 풀어야 한다는 것을 배웠다.

지난번에도 비슷한 고민을 한적이 있는데 그때는 dfs로 경우의 수 세기를 고민했었다. 그 문제와 비슷한 고민을 했고, 답은 맞게 나오나 시간초과가 나기 때문에 이 글을 쓰게 되었다.

 

먼저 일반적인 dfs나 bfs의 구현방법은 dfs든 bfs든 방문배열(보통 visited배열)을 만들고 탐색한 점은 방문했음을 표시하여(visited=True) 다시 방문하지 않는 것이다.

이렇게 했을때 dfs, bfs 모두 인접행렬을 탐색할 때는 시간복잡도가 O(n^2), 인접 리스트를 탐색할 때는 시간복잡도가 O(n+e)이다.

 

이 visited 배열에 대해 고민하게 된 계기는 문제 '2056번: 작업'이다. 2056번 문제에 대해 간략하게 소개하자면, 수행해야 할 작업 N개가 있고 각각의 작업마다 걸리는 시간이 있다. 또한 작업들 간에는 선행관계가 존재한다.

이 문제도 처음에 보고 선행 관계가 존재하고( 부모, 자식 노드) 사이클이 존재하지 않기에 트리 구조를 생각하였고 따라서 dfs로 풀어야겠다 생각 했었다.

 

2056번의 테스트 케이스를 트리로 나타내면 다음 그림과 같다.

  dfs에 방문배열을 사용하여 탐색한다면 1->2->3->7순으로 처음에 탐색할 것이고 그 다음은 5를 탐색할 것이다. 왜냐하면 1, 2, 7번 노드는 이미 방문했기 때문이다. 각 경로 중 작업시간의 합이 가장 작은 경로를 찾아야 했기에 고민을 했었고 해결 방법으로 두가지를 생각했었다. 

 

첫번째 방법은 visited배열을 사용하지 않고 dfs를 사용하는 것이다. 이렇게 되면 이미 탐색한 노드도 다시 탐색하기에 방문한 노드들의 탐색시간들의 합을 구할 수 있다. 이 방법의 문제는 재귀함수이기때문에 시간복잡도가 커진다는 점이다.

두번째 방법은 탐색한 노드들 중 작업시간이 작은 값을 다른 배열에 저장 하는 것이다. 그리고 이는 DP풀이이다.

 

이번에 푼 문제인 17070번 문제도 고민한 점이 같다. 2차원 배열의 끝점(배열의 길이가 N일때, row=N-1, col=N-1인 점)에 도달할 수 있는 경우의 수를 구하는 문제이다.

끝점(2056번 문제에서는 최하단 자식노드)에 도달하는 경우의 수를 구하는 문제라는 점에서 두 문제는 같다. 또한 자료가 각각 행렬 / 트리이기 때문에 보자마자 dfs/bfs 풀이를 고민하게 되는 점도 같다.

 

17070번 문제를 푼 다른 사람들도 같은 고민을 한 것 같았다. 그 중 dfs를 정말 최적화 해서 푼 사람도 있으나 그 코드도 pypy3로 제출해야만 통과를 할 수 있었다. 그 풀이 역시 내가 전에 했던 고민처럼 visited배열을 만들지 않고 완전탐색하는 식이였다. 그 코드는 다음과 같다.

from collections import deque
import sys
input = sys.stdin.readline
def dfs(x, y, direction):
    global count
    if x == n - 1 and y == n - 1: count += 1
    if direction == 0:
        if y + 1 < n and s[x][y + 1] == 0: dfs(x, y + 1, 0)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
    elif direction == 1:
        if x + 1 < n and s[x + 1][y] == 0: dfs(x + 1, y, 1)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
    elif direction == 2:
        if y + 1 < n and s[x][y + 1] == 0: dfs(x, y + 1, 0)
        if x + 1 < n and s[x + 1][y] == 0: dfs(x + 1, y, 1)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
n = int(input())
s = [list(map(int, input().split())) for i in range(n)]
count = 0
dfs(0, 1, 0)
print(count)

 파이프가 놓여진 형태가 가로인지 세로인지 아니면 대각선인지를 dfs의 인자로 넣어 조건문의 조건들을 확 줄이고, 파이프의 오른쪽 점만 사용하여 배열의 크기를 줄였음에도 pyp3로 제출하지 않으면 시간초과가 나는 풀이이다.

 

DP로 풀어야 파이썬으로 제출해도 통과한다.

import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for i in range(n)]
result = [[[0 for i in range(n)] for i in range(n)] for i in range(3)]
result[0][0][1] = 1
for i in range(2, n):
    if s[0][i] == 0:
        result[0][0][i] = result[0][0][i - 1]
for i in range(1, n):
    for j in range(2, n):
        if s[i][j] == 0 and s[i - 1][j] == 0 and s[i][j - 1] == 0:
            result[2][i][j] = result[0][i - 1][j - 1] + result[1][i - 1][j - 1] + result[2][i - 1][j - 1]
        if s[i][j] == 0:
            result[0][i][j] = result[0][i][j - 1] + result[2][i][j - 1]
            result[1][i][j] = result[1][i - 1][j] + result[2][i - 1][j]
print(result[0][n - 1][n - 1] + result[1][n - 1][n - 1] + result[2][n - 1][n - 1])

2056번 문제와 17070번 문제를 풀어보고, 다른사람들이 통과한 코드와 실패한 코드들을 모두 살펴본 후 내린 결론은 

자료가 트리나 행렬의 형태라 하여 무조건 dfs, bfs로 접근해서는 안된다는 것이다.

특히 경우의 수를 구해야 하는 문제인 경우 DP로 접근해야 함을 알 수 있었고 visited배열을 사용안한 dfs, bfs로도 풀 수는 있지만 시간복잡도가 너무 커지기 때문에 문제의 난이도가 높은 경우 시간초과가 나므로 DP로 접근하는 것이 맞을 것이다.