3109번: 빵집 / gold 2 / DFS, 그리디

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

3109번: 빵집

'''
3109번: 빵집 / gold 2 / DFS, 그리디
'''
import sys

input = sys.stdin.readline

dx = [-1, 0, 1]


def solve(x, y):
    if y == C - 1:
        return True
    for i in range(3):
        nx = dx[i] + x
        if 0 <= nx < R and graph[nx][y + 1] == '.' and not visited[nx][y + 1]:
            visited[nx][y + 1] = True
            if solve(nx, y + 1):
                return True
    return False


R, C = map(int, input().split())
graph = []
for _ in range(R):
    graph.append(list(map(str, input().rstrip())))
visited = [[False for _ in range(C)] for _ in range(R)]

ans = 0
for i in range(R):
    if graph[i][0] == '.':
        if solve(i, 0):
            ans += 1
print(ans)

코드 리뷰

- 문제 해결도 못하고, 1시간 소요가 되어서 구글링을 했습니다.

 

<잘못된 문제 이해>

- 구글링을 한 후, 문제를 잘못 이해하고 접근했다는 것을 알게 되었습니다!

'가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.'

- 저는 첫째 열을 첫째 행으로 착각해서 계속 접근하고 있었습니다. 따라서 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 연결이 이해가 안됬고, 잘못된 파이프를 설치할 수 밖에 없었습니다.

- 즉, graph에서 파이프가 왼쪽->오른쪽으로 생성하는 문제였지만, graph에서 파이프가 위->아래로 생성하는 것으로 이해했던 것!

 

<이미 정답 로직을 알게 됨>

- 구글링을 통해 이미 정답 코드를 이해하게 되었고, dfs를 통해서 이미 방문했던 곳을 표시하는 것이 중요하다는 것을 알게 되었습니다.

- 이미 정답 코드를 이해하게 되었지만, 그래도 최대한 제가 이해한 대로 코드를 짜고 제출을 했습니다!

- 어려운 포인트에서 충분히 생각하는 시간이 있어야 했는데, 문제를 완전히 잘못 이해하는 바람에 그런 시간을 가지지 못한 것 같습니다.