less than 1 minute read

문제

접근 방법

최대한 많은 파이프를 연결해야 하는데 어떤 파이프가 아래로 가로지르면서 연결된다면 그 아래 위치들의 파이프는 연결된 빵집 위치의 위에 있는 위치들에 연결이 될 수 없다. $\rightarrow$ 즉, 최대한 파이프가 위에 연결되어야 한다는 것을 통해 Greedy 문제인 것을 알 수 있다.

Backtracking을 하기 위해서 DFS를 사용해야 하고 최대한 위에 연결되도록 하기 위해 moves를 (-1,1),(0,1),(1,1)으로 정의하여 오른쪽 위로 제일 우선적으로 가게 하였다.

Backtracking 문제를 조금 많이 풀어야 할 것 같다.. DFS를 드럽게 못 짠다.

정답 코드


import sys

input = sys.stdin.readline

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

maps = []
for _ in range(r):
  maps.append(list(input().rstrip()))


# 건물에서 시작해서 최대한 빵집의 위에부터 차례대로 도착하도록 moves 순서 다음과 같이 함
moves = [(-1,1),(0,1),(1,1)]

def dfs(start_h, start_w):
  maps[start_h][start_w] = 'x'
  # 도착지라면
  if start_w == c-1:
    return True
    
  for dh,dw in moves:
    new_h, new_w = start_h+dh, start_w+dw
    if 0<=new_h<r and 0<=new_w<c and maps[new_h][new_w]=='.':
      if dfs(new_h, new_w):
        return True

  return False


nums = 0

for h in range(r):
  result = dfs(h,0)
  if result:
    nums+=1

print(nums)

You May Also Enjoy