[백준 python] 14502번 연구소

문제 링크

14502번: 연구소

문제 설명

• 빈 공간, 벽, 바이러스로 구성된 2차원 array를 입력받아 빈 공간 세 곳에 벽을 세운 후 바이러스가 퍼질 수 없는 영역의 수를 세는 문제
• 구현해야 하는 내용은 빈 공간에 ${}^{1)}$세 개의 벽을 세우는 것, ${}^{2)}$바이러스가 퍼질 수 있는 영역을 BFS로 탐색하는 것, ${}^{3)}$감염되지 않은 영역을 세는 것

고민한 부분

• 아직 순열이나 조합을 응용하는 문제에 익숙하지 않아 긴 시간동안 고민을 했음
• 재귀 방식으로 3개의 블럭을 쌓은 후 BFS를 탐색하는데 line 58~에 가지치기 조건을 추가해 시간을 절약함
  • 처음부터 탐색하지 않아도 될 조건을 고민하기보다 시간을 고려하지 않고 정답을 찾을 수 있는 코드를 작성한 후에 고민하는 것이 효율적인 것 같음
  • 그리고 만약 itertools 라이브러리를 활용해 통과할 수 있다면 라이브러리 활용하는 것이 훨씬 효과적
• 문제를 계속 풀다보니 재귀 형태로 순열과 조합을 구하는 것에 익숙해고 코드 패턴이 눈에 익고 있는 것 같음

 

	import sys
	import copy
	from collections import deque
	def BFS:
	global TABLE
	dr = [-1,1,0,0]
	dc = [0,0,-1,1]
	table = copy.deepcopy$TABLE$
	q = deque
	# 초기값 insert
	for r in range$R$:
	for c in range$C$:
	if table[r][c] == 2:
	q.append$(r,c$)
	# 순회
	while$len(q$ != 0):
	# 상하좌우
	$r,c$ = q.popleft
	# do sth
	table[r][c] = 2
	# expand
	for i in range$4$:
	nr, nc = r + dr[i], c + dc[i]
	# 예외 처리
	## 범위 밖
	if $nr<0 or nr>=R$ or $nc<0 or nc>=C$:
	continue
	## 아직 오염 안된 영역이면 queue에 넣기
	if table[nr][nc] == 0:
	q.append$(nr,nc$)
	## 남은 0 영역 세기
	cnt = 0
	for r in range$R$:
	for c in range$C$:
	if table[r][c] == 0:
	cnt += 1
	return cnt
	def DFS$r, c, visited,depth = 0$: ## 0, 0에서 시작하면 okay
	global TABLE, solution
	# 상상 상좌 좌 하좌 하 하우 우 상우
	dr = [-1, -1, 0, 1, 1, 1, 0, -1]
	dc = [0, -1, -1, -1, 0, 1, 1, 1]
	## 3개 선택
	if depth == 3:
	# 만약 세번째 기둥이 차단하지 못했으면 BFS 생략
	# 벽 맞닿음 vs 벽 떨어져있음
	cnt = 0
	is_wall = 0
	for i in range$8$:
	nr = r + dr[i]
	nc = c + dc[i]
	if nr < 0 or nr>=R or nc<0 or nc>=C:
	is_wall = 1
	continue
	if TABLE[nr][nc] ==0:
	cnt += 1
	if is_wall == 1 and cnt == 5:
	return
	elif is_wall == 0 and cnt >=7:
	return
	# BFS 돌리기 --> 안전 영역 count 리턴
	bfs = BFS
	if bfs > solution:
	solution = bfs
	return
	## dfs stack
	for r_ in range$r, R$:
	for c_ in range$C$:
	#빈 공간인지 확인
	if TABLE[r_][c_] == 0 and visited[r_][c_] == 0:
	# do sth : 벽 세우기 & visited ack
	TABLE[r_][c_] = 3
	visited[r_][c_] = 1
	# next :
	DFS$r_,c_, visited,depth + 1$
	# undo sth
	TABLE[r_][c_] = 0
	visited[r_][c_] = 0
	if __name__ == "__main__":
	turn_in = 1
	if turn_in == 0:
	sys.stdio = open$'test_case.txt'$
	R, C = list$map(int,sys.stdio.readline($.split))
	TABLE = [list$map(int, sys.stdio.readline($.split)) for i in range$R$]
	else:
	R, C = list$map(int,sys.stdin.readline($.split))
	TABLE = [list$map(int, sys.stdin.readline($.split)) for i in range$R$]
	##
	VISITED = [[0]*C for i in range$R$]
	solution = 0
	DFS$0,0,VISITED$
	print$solution$

view raw boj_14502.py hosted with ❤ by GitHub