[백준-파이썬] 3109(Gold2)/dfs : 빵집

<문제출처>

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

3109번: 빵집

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

 

<문제풀이시 고민했던 내용들>

''' 지출을 줄이자 -> 가스비가 너무 큼
근처 빵집 가스관에 몰래 파이프를 설치해 가스를 훔치자

왼쪽열부터 오른쪽열까지 열결할 수 있는 선의 최대 개수 제일 위쪽으로 붙이도록 우선순위 주면 되지 않나?? - (그리디?)
<아이디어>
오른쪽위 -> 오른쪽 -> 오른쪽아래 (우선순위를 두고 무조건 밀착해서 가야 최대로 많은 파이프길이 생걸 것이다)

<수도코드>
for (왼쪽열 맨위부터 맨 아래까지 반복):
    우선순위에따라 오른쪽으로 파고들면서 지나왔던 길들을 체크해놓는다[(1, 1), (1, 2)..] 한다.
    if (만약 오른쪽 끝까지 도착못했는데 갈 곳이 없다면):
        pass
    if (오른쪽 끝에 다 왔다면):
        파이프개수 카운트
        방문체크들을 탐색하여 arr배열 방문처리

이 문제는 그리디 아이디어를 적용해서 방문처리 초기화를 하지 않아도 되는 문제이다.

 

그 이유는 만약 (0, 0)행에서 출발한 첫번 쨰 파이프 선이 오른쪽 끝까지 도착하지 못했다고 생각해보자.

이 말은 즉 (0, 0)행 아래에 있는 모든 출발점부터는 첫번 째 파이프가 지나갔던 길을 가봤자 어차피 못가는 길이기 때문에 굳이 방문처리를 초기화해서 한번 더 확인할 필요가 없기 떄문이다.( -> phthon사용 시 시간 초과)

 

또한 pypy3로 해서 통과 받았다.. 다른 사람 코드를 확인해보니 알고리즘은 거의다 동일하고 아주 살짝의 문법상의 성능으로 python3, pypy3 성능이 갈리는 것 같다. -> 앞으로 그래프탐색, 완탐, 백트래킹은 pypy3로 일단 먼저 돌려보자

 

 

최종코드

import sys; input = sys.stdin.readline

def is_range(nx, ny):
    return 0 <= nx < R and 0 <= ny < C


def dfs(x, y):
    arr[x][y] = 'x'
    
    if y == C - 1:
        return True
    
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy

        if is_range(nx, ny) and arr[nx][ny] == '.':
            if dfs(nx, ny):
                return True

    return False


# 변수 입력 및 선언
R, C = map(int, input().split())
arr = [list(input().strip()) for _ in range(R)]
dxs, dys = [-1, 0, 1], [1, 1, 1]
ans = 0

for i in range(0, R):
    # 시작좌표, 방문체크리스트
    x, y = i, 0

    # 다 방문했는데 오른쪽 끝이라면
    if dfs(x, y):
        ans += 1

print(ans)