[BOJ] Q3109 빵집

[BOJ] Q3109 빵집

Question

Language: Python

Difficulty: Gold 2

해당 문제는 파이프라인을 설치할 때 최대한 윗쪽 좌표를 우선적으로 탐색하여 파이프라인 설치 가능 여부를 조사해서 설치를 진행한다.

처음에는 bfs을 활용해서 첫 열에서 마지막 열 까지 도달가능한 경로가 있는지 파악하려고 했다.

Failed Solution

import sys
from collections import deque
def print_board(board):
    for row in board:
        print(*row)

def solution():
    visited=[[False] * n_cols for _ in range(n_rows)]

    dy=[-1,0,1]
    dx=[1,1,1]
    pipeline_count=0
    for start_row in range(n_rows):
        queue=deque([(start_row,0,[])])
        pipeline_path=[]
        while queue:
            row,col,path=queue.popleft()
            #끝점에 도달한 경우
            if col == (n_cols-1):
                pipeline_path=path
                break

            for dir in range(3):
                next_row=row + dy[dir]
                next_col=col + dx[dir]

                #격자를 벗어나는 경우
                if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col >=n_cols:
                    continue
                
                #벽인 경우
                if board[next_row][next_col]== "x":
                    continue
                    
                #이미 파이프 라인이 설치되어 있는 경우
                if visited[next_row][next_col]:
                    continue
                queue.append((next_row,next_col,path+[dir]))
        
        #끝열에 도달한 경우 --> 파이프라인을 설치할 수 있는 경우
        if pipeline_path != []:
            current_row,current_col=start_row,0
            visited[current_row][current_col]=True

            for dir in pipeline_path:
                current_row += dy[dir]
                current_col += dx[dir]
                visited[current_row][current_col]=True
            
            pipeline_count+=1
    
    print(pipeline_count)
if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    board=[list(input()) for _ in range(n_rows)]
    
    solution()

하지만 위와 같이 하면 여러 개의 path을 동시에 저장해야되므로 메모리 초과가 발생하게 된다.

따라서, 경로를 메모리에 저장하지 않고 우선적으로 탐색을 통해 도달 가능한 경로가 있는지 파악하기 위해 dfs을 활용한다.

핵심 로직

아래의 dfs 경우에 대한 조건 검사를 수행하여 참일떄(경로가 탐색된 경우) return을 수행하여 더 이상 진행하지 않도록 하는 것이 중요하다.

if find_path(next_row,next_col,path+[(next_row,next_col)]):
    return True

Solution

def find_path(row,col,path):
    global visited,pipeline_count
    if col == (n_cols-1):
        pipeline_count+=1
        return True
        
    for dir in range(3):
        next_row=row + dy[dir]
        next_col=col + dx[dir]

        #격자를 벗어나는 경우
        if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col >=n_cols:
            continue
        
        #벽인 경우
        if board[next_row][next_col]== "x":
            continue
            
        #이미 파이프 라인이 설치되어 있는 경우
        if visited[next_row][next_col]:
            continue
        visited[next_row][next_col]=True
        if find_path(next_row,next_col,path+[(next_row,next_col)]):
            return True
    return False

def solution():
    for start_row in range(n_rows):
        find_path(start_row,0,[(start_row,0)])
    
    print(pipeline_count)
if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    board=[list(input()) for _ in range(n_rows)]
    visited=[[False] * n_cols for _ in range(n_rows)]
    dy=[-1,0,1]
    dx=[1,1,1]
    pipeline_count=0
    solution()