[Python] 백준 3109 빵집

문제 링크 : https://www.acmicpc.net/problem/3109

3109번: 빵집

1. 접근 방법

좋지 않은 습관이지만, 문제 카테고리를 먼저 확인하고 접근했고, 그리디라는 카테고리만 생각하여 처음에는 잘못 접근했었다.

결론적으로, 파이프가 생성될 수 있는 시작점, 끝점을 이어가면서 해결했는데, 시작점부터 위에서, 아래로 확인을 하면 기존 파이프 때문에 새로 생성하지 못하는 경우는 없고, 이 방법으로 해결했다. 서로 겹치지 않고, 세 방향 탐색이라는 부분에서 그리디를 카테고리로 포함한 것 같은데, 그래프 탐색 문제가 더 적절하다고 생각한다.

 

 

2. 풀이 코드

🖥python 코드

import sys
input = sys.stdin.readline


def search(row: int, col: int) -> int:
    global r, c, grid
    # 범위를 벗어남
    if row < 0 or row >= r:
        return 0
    # 마지막까지 도착
    if col == c:
        return 1
    # 건물있음
    if grid[row][col] == 'x':
        return 0
    # 지나간 길 표시
    grid[row][col] = 'x'
    # 탐색
    if search(row - 1 , col + 1):
        return 1
    if search(row, col + 1):
        return 1
    if search(row + 1, col + 1):
        return 1
    return 0


r, c = map(int, input().split())

grid = [list(input().strip()) for _ in range(r)]

pipe_count = 0
for i in range(r):
    if search(i, 0):
        pipe_count += 1
print(pipe_count)

📕코드 해설

가장 위에서부터 아래로, 그리고 파이프 배치도 오른쪽-위, 오른쪽, 오른쪽-아래 순서로 탐색했다.

그러면, 연결할 수 있는 파이프는 열결 되었기 때문에 다른 파이프가 지나가지 못하고, 연결할 수 없는 파이프는 어짜피 지나가지 못하는 경로이므로, 두 경우 모두 지나가는 경로마다 모두 표시하며 진행했다.

문제를 모두 진행하면, 예제 2의 경우 다음과 같은 결과가 나온다.

검정색은 원래 건물 위치이고, 각 파이프는 모두 'x'로 표시했지만, 같은 파이프가 같은 색을 같도록 표시했다.

이 경우, 마지막 파이프만 지나가지 못하는데, 다른 경우에서 파이프가 지나가지 못하더라도 표시를 남겨두고 진행해도 된다.

함수의 리턴 값을 0/1로 한 것은, 결괏값에 바로 더하려고 했었는데, 다른 부분은 구현하고 나서 깜빡하고 적용하지 않았다.

 

 

3. 생각 정리

문제를 풀기 전 카테고리를 먼저 보는 습관을 줄여야겠다.

특정 방법으로만 생각하게 되는 부분도 있고, 생각을 덜하게 되는 것 같다.