17070 / 파이프 옮기기 1 파이썬

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

bfs, dfs, 누적합 총 세가지 방법으로 풀어봤다.

당연히 bfs, dfs는 시간초과가 났고 마지막 누적합에서 통과됐다.

 

시간은 bfs > dfs 이다. bfs의 경우 deque에 append, popleft()하는 과정에서 시간이 소요되는듯 하다. 

 

1. 누적합을 이용한 코드 (성공)

N = int(input())
maps=[]
for _ in range(N):
    maps.append(list(map(int,input().split())))
visited = [[[0,0,0] for _ in range(N)] for _ in range(N)]
visited[0][1][0] = 1
for i in range(N):
    for j in range(1,N):
        if j + 1 < N and maps[i][j + 1] != 1:
            visited[i][j+1][0] += visited[i][j][0] +visited[i][j][2]
        if i + 1 < N and maps[i + 1][j] != 1:
            visited[i+1][j][1] += visited[i][j][1] + visited[i][j][2]
        if i + 1 < N and j + 1 < N and maps[i][j + 1] != 1 and maps[i + 1][j] != 1 and maps[i + 1][j + 1] != 1:
            visited[i + 1][j+1][2] += visited[i][j][2] + visited[i][j][1] +visited[i][j][0]

# for visit in visited:
#     print(visit)
print(sum(visited[-1][-1]))

변수명이 visited인 이유는 이전의 문제를 풀다가 걍 쓴것... visited가 누적합에 사용되는 3차원 변수다. visited의 각 요소는 [가로,세로,대각선]이고 의미하는 바는 해당 [i][j]에 출구를 댄 파이프의 수이다. 즉, [3,4,5]라면 해당 인덱스에 가로로 3개, 세로로 4개, 대각선으로 5개의 파이프가 출구를 댄것이다.

 

그리고 그냥 포문 돌리면 끝난다. 굉장히 간단한 코드지만 보자마자 완전탐색을 할 생각을 했고 그 결과 많은 시간을 뺏겼다. 해당 문제를 보면 파이프는 우하향의 방향으로만 움직이므로 방향이 일정하다. 그러므로 충분히 누적합을 생각할 수 있었을텐데 못했다 ㅠㅠ

 

2. dfs - 시간초과

N = int(input())
maps=[]
for _ in range(N):
    maps.append(list(map(int,input().split())))
answer = 0
def dfs(x,y,type):
    if x==N-1 and y==N-1:
        global answer
        answer += 1
        return

    if type == 1 or type == 3:
        if y + 1 < N and maps[x][y + 1] != 1:
            # print("가로-가로 추가",pipe[0],pipe[1]+1)
            dfs(x,y+1,1)
    if type == 2 or type == 3:
        if x + 1 < N and maps[x + 1][y] != 1:
            #print("세로-세로 추가",pipe[0]+1,pipe[1])
            dfs(x+1,y,2)

    if x + 1 < N and y + 1 < N and maps[x][y + 1] != 1 and maps[x + 1][y] != 1 and maps[x + 1][y + 1] != 1:
        # print("세로-대각선 추가",pipe[0]+1, pipe[1]+1)
        dfs(x+1,y+1,3)

dfs(0,1,1)
print(answer)

 

3. bfs - 시간초과

from collections import deque

N = int(input())
maps=[]
for _ in range(N):
    maps.append(list(map(int,input().split())))
stack = deque()
stack.append([0,1,1])
answer = 0

while len(stack)!=0:
    pipe = stack.popleft() #pipe에는 가능한 pipe만 들어있음
    #print("현재 파이프 : ",pipe[0],pipe[1],pipe[2])
    if pipe[0]== N-1 and pipe[1] == N-1: #끝에 도달하면 answer += 1
        answer += 1
        continue
    type = pipe[2]
    if type == 1: #가로인경우
        if pipe[1]+1 < N and maps[pipe[0]][pipe[1]+1] != 1:
            #print("가로-가로 추가",pipe[0],pipe[1]+1)
            stack.append([pipe[0],pipe[1]+1,1])
        if pipe[0]+1 < N and pipe[1] + 1< N and maps[pipe[0]][pipe[1]+1] != 1 and maps[pipe[0]+1][pipe[1]] != 1 and maps[pipe[0]+1][pipe[1]+1] != 1:
            #print("가로-대각선 추가",pipe[0]+1, pipe[1]+1)
            stack.append([pipe[0]+1, pipe[1]+1,3])
    elif type == 2: #세로인경우
        if pipe[0]+1 <N and maps[pipe[0]+1][pipe[1]] != 1:
            #print("세로-세로 추가",pipe[0]+1,pipe[1])
            stack.append([pipe[0]+1,pipe[1],2])
        if pipe[0]+1 < N and pipe[1] + 1< N and maps[pipe[0]][pipe[1]+1] != 1 and maps[pipe[0]+1][pipe[1]] != 1 and maps[pipe[0]+1][pipe[1]+1] != 1:
            #print("세로-대각선 추가",pipe[0]+1, pipe[1]+1)
            stack.append([pipe[0]+1, pipe[1]+1,3])
    else : #대각선인 경우
        if pipe[1]+1 < N and maps[pipe[0]][pipe[1]+1] != 1:
            #print("대각-가로 추가",pipe[0],pipe[1]+1)
            stack.append([pipe[0],pipe[1]+1,1])
        if pipe[0]+1 <N and maps[pipe[0]+1][pipe[1]] != 1:
            #print("대각-세로 추가",pipe[0]+1,pipe[1])
            stack.append([pipe[0]+1,pipe[1],2])
        if pipe[0]+1 < N and pipe[1] + 1< N and maps[pipe[0]][pipe[1]+1] != 1 and maps[pipe[0]+1][pipe[1]] != 1 and maps[pipe[0]+1][pipe[1]+1] != 1:
            #print("대각-대각선 추가",pipe[0]+1, pipe[1]+1)
            stack.append([pipe[0]+1, pipe[1]+1,3])
print(answer)