[Python] 백준 3109. 빵집

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

3109번: 빵집

그리디 알고리즘 + BFS 문제.

 

최대한 많은 가스관을 배치하기 위해서는, 가급적이면 가스관이 우상향이 되어야 한다.

따라서 우상향 / 직진 / 우하향 순서대로 파이프를 설치할 수 있는지 DFS로 확인해야 한다.

 

 

	import sys
	r, c = map(int, sys.stdin.readline().split())
	maps = []
	for y in range(r):
	arr = list(sys.stdin.readline().replace("\n",""))
	maps.append(arr)
	# 많은 파이프를 심으려면, 최대한 우상향으로 접근해야 함.
	dirs = [(-1,1),(0,1),(1,1)]
	end_line = len(maps[0])-1
	def connect_pipe(y: int, x: int) -> bool:
	# 현재 위치에 파이프 생성
	maps[y][x] = 'x'
	if x == end_line:
	return True
	for dy, dx in dirs:
	ny, nx = y+dy, x+dx
	# 다음 위치에 파이프 생성이 가능한지 확인
	if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]) and maps[ny][nx] == ".":
	if connect_pipe(ny, nx):
	# 끝까지 설치가 가능할 경우 이 분기로 진입하게 됨.
	return True
	return False
	answer = 0
	for y in range(len(maps)):
	if connect_pipe(y,0):
	answer += 1
	print(answer)

view raw [백준] 빵집.py hosted with ❤ by GitHub