[백준/파이썬] 3109번 빵집 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 3109번 빵집
• 문제풀이 코드 GitHub 링크
• 제출 언어: PyPy 3

풀이

문제

왼쪽 열이 빵집, 오른쪽 열이 가스를 훔쳐올 빵집의 파이프 라인일 때, 이 둘을 연결하는 파이프 라인의 최대 갯수는?

(단, 파이프는 오른쪽, 우상단, 우하단 세방향으로만 뻗을 수 있습니다)

회색으로 칠해진 곳은 입력으로 x가 들어오며, 해당 방향으로는 파이프를 뻗을 수 없고, 다른 파이프가 이미 있는 칸에도 파이프를 뻗을 수 없습니다.

코드

import sys;read=sys.stdin.readline
r,c=map(int,read().split())
l=[list(read().strip())for _ in range(r)]
d=(-1,0,1)
stack,a=[],0

for i in range(r):
    ci=i
    cj=j=c-1
    while True:
        if cj<1:
            while stack:
                l[ci][cj]='o'
                ci,cj=stack.pop()
            l[ci][cj]='o'
            a+=1
            break
        f=False
        for k in range(3):
            if 0<=ci+d[k]<r and l[ci+d[k]][cj-1]=='.':
                f=True
                stack.append((ci,cj))
                ci,cj=ci+d[k],cj-1
                break
        if not f:
            l[ci][cj]='_'
            try:ci,cj=stack.pop()
            except:break
            
print(a)

설명

백트래킹으로 풀 수 있는 문제입니다.

[i][j]에 있는 파이프가 [i-1][j+1], [i][j+1], [i+1][j+1]로만 갈 수 있다는 말은 다시말해,

[i][j]에 있는 파이프는 [i-1][j-1], [i][j-1], [i+1][j-1]에서만 올 수 있다는 말이됩니다.

이를 활용해 백트래킹 해봅시다. 시작점을 우리 빵집이 아니라 상대 빵집으로 잡고, 상대 빵집부터 우리 빵집쪽으로 파이프를 당겨오는겁니다.

파이프가 지나오는 경로는 stack에 넣고, 모든 길이 막혀있으면 pop하여 다시 시도합니다.

이렇게 stack이 비기 전에 우리 빵집에 도달했다면, 지나온 경로를 모두 체크해주고 카운트를 증가시킵니다. 이렇게 하면 파이프를 장애물 취급하여 해당 칸으로는 다른 파이프가 오지 않습니다.

이걸 반복하면 상대 빵집 열의 모든 칸에 대해 검사가 끝났을 때 카운트에 파이프라인의 최대 개수가 저장됩니다.

다만 파이썬 특유의 느린 속도 때문에 제 코드로는 제출언어 Python 3로 통과가 되지 않더군요. PyPy 3로 제출하면 통과됩니다.

---

• 백준 문제풀이 전체 목록 보기

---