백준 3109번 빵집 (Python)

R * C 크기의 지도가 주어집니다. 첫 번째 열에서 마지막 열까지 가스관을 연결하려고 할 때, 건물이 있는 곳이나 가스관이 이미 설치된 곳에는 새로운 가스관을 설치하지 못합니다.

모든 가스관은 첫 번째 열에서 마지막 열로 이동을 하고 한 지점에서 다음 지점으로 가스관을 연결하는 방법은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 방향 3가지가 있습니다.

가스관을 설치할 수 있는 최대 개수를 구하는 문제입니다.

 

 

아이디어 1. (모든 경우의 수 탐색)

모든 경우의 수를 dfs로 재귀를 통해 가장 많은 경우의 수를 찾아보려고 했습니다.

하지만, 문제에서 주어진 조건이 (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)으로 모든 경우의 수를 찾아보기 위해서는 최악의 경우 10,000 * 500 * 3 이상의 경우의 수를 살펴볼 수 있을 것이라고 생각했습니다. 너무 많은 경우의 수를 살펴봐야하므로 시간 초과가 발생할 것 같아 다른 방법을 찾아보게 되었습니다.

 

아이디어 2. (각 지점을 지나는 시작점 저장)

모든 경우의 수를 살펴보지 않고 건물 사이를 지나갈 수 있는 가스관의 최대 개수를 구해보도록 했습니다.

R*C 크기의 배열의 원소를 배열로 3차 배열의 변수 안에 각 칸을 지나가는 시작지점을 기록해둠으로써 어떤 지점에 몇 개의 가능성이 있는지 확인해보려고 했습니다.

하지만, 위와 같이 모든 지점에 대해 기록을 한다 해도, 한 지점에 가스관이 설치된다면 모든 경우의 수는 처음부터 다시 구해야되기 때문에 이 또한 시간이 오래 걸릴 것 같아 더 이상 진행하지 않았습니다.

 

아이디어 3. (탐색 순서, 이동 순서 지정)

모든 경우의 수를 살펴보지 않고 항상 최대 경우의 수를 찾을 방법을 생각해보았습니다.

"건물 사이로 가스관이 생기고 결국 마지막 열까지 도달한다면, 이 경로는 어떤 시작지점에서 시작한 것이든 상관없지 않을까?" 라는 생각을 하게 되었습니다.

하지만, 이 또한, 하나의 가스관을 지나가는 가스관이 생긴다면 다른 가스관을 설치할 때 영향을 줄 것이라 생각해서 진행하기 어려울 것으로 보였습니다.

 

여기서 더 나아가는 생각을 한 것이, 어떤 시작점에서든 결국 마지막에 도달한다면 정답에 +1 되는 것은 모두 똑같으니 그냥 첫 번째 열의 맨 위에서부터 갈 수 있는 길을 찾아보자. 그리고 다음칸으로 이동하는 방향의 순서를 오른쪽 위, 오른쪽, 오른쪽 아래로 지정해준다면, 어떤 지점을 가장 먼저 지날 수 있는 시작점은 첫 번째 열의 위에 있는 칸부터 순서대로이고 이 지점을 지나서 마지막 열에 도착한다면 해당 경우의 수를 정답에 포함하는 것이 최대 경우의 수를 구하는 방법이라고 생각했습니다.

 

즉, 첫 번째 열의 위에서부터 아래의 순서로 이동을 하고, 다음칸으로 이동하는 순서를 대각선 위, 오른쪽, 대각선 아래로 이동하면서 마지막열에 도착한다면 해당 경우를 포함하는 것이 최대의 경우의 수를 구하는 방법이라고 생각했습니다.

 

 

 

풀이

dfs 순회는 다음과 같은 경우 진행했습니다.

 

1. x,y에서 y가 마지막 열에 도착할 경우 True를 반환합니다.

 

2. (x-1, y+1) , (x, y+1), (x+1, y+1) 순서로 이동을 합니다. 이 때, 다음 칸이 아직 방문을 안 했을 경우, 건물이 없는 칸일 경우에만 다음칸으로 이동합니다. 이동할 수 있는 칸은 모두 방문했음을 표시해줍니다.

 

3. dfs 반환 값이 True일 경우 2.에서의 이동 관련 반복문을 벗어나고 True를 반환해줍니다. dfs 반환 값이 False일 경우 계속 반복문을 진행합니다. 마지막까지 dfs 반환 값이 False일 경우(마지막 열에 도달하지 못하는 경우) False를 반환해줍니다.

 

4. 위의 순서를 0부터 R-1까지 반복해주고, dfs(i,0) 값이 True를 반환할 경우 answer를 1 증가해줍니다.

 

소스 코드

import sys
input = sys.stdin.readline


def dfs(x, y):
    global R, C
    if y == C-1:
        return True

    flag = False
    for i in range(3):
        nx, ny = moves[i][0]+x, moves[i][1]+y

        if not (0 <= nx < R and 0 <= ny < C) or visited[nx][ny] or roads[nx][ny] == 'x':
            continue

        visited[nx][ny] = True
        if dfs(nx, ny):
            flag = True
            break

    return flag


R, C = list(map(int, input().split()))
roads = [list(input()) for _ in range(R)]
visited = [[False for _ in range(C)] for __ in range(R)]
moves = [(-1, 1), (0, 1), (1, 1)]
answer = 0

for r in range(R):
    visited[r][0] = True
    if dfs(r, 0):
        answer += 1

print(answer)

 

 

 

 

오늘은 그래프 관련 문제를 풀게 되었습니다. 실제 풀이에 관련된 아이디어를 만들어내는데 오래걸렸지만, 아이디어들을 조합해 해결할 수 있었습니다.