[백준] 1941 소문난 칠공주

 

---

소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하는 문제이다. 브루트 포스, 백트래킹 알고리즘 유형에 해당한다.

 

단, 소문난 칠공주는 가로 또는 세로로 모두 인접해야하며, 이다솜파가 과반수(4)이상 이어야 한다.

 

• 여학생반의 크기는 5*5 크기로 고정되어 있기 떄문에 학생들을 0 ~ 24로 인덱싱한다.
• n번 학생의 위치는 (n / 5,  n%5 )에 위치한다.
• DFS를 통해 0번 부터 24번 학생까지 순회한다.
• 현재 학생을 I라고 하면 I 학생은 이다솜파, 임도연파 중 하나이며 소문난 칠공주에 포함할 지 결정한다.
• 7명을 모두 소집한 경우 모두 인접한지 확인한다.
• 시작점을 기준으로 상, 하, 좌, 우 인접한 노드를 DFS로 방문하여 인접한 경우 카운트를 1 증가시키고 7이 되는 경우 모두 인접한 것으로 한다.

 

Python

 

	from sys import stdin
	readline = stdin.readline
	_map = [list(readline()) for _ in range(5)]
	S = []
	include = [False] * 25
	ans = 0
	dr = (1, -1, 0, 0)
	dc = (0, 0, 1, -1)
	def solve(idx, yn, cnt):
	global ans
	if yn >= 4 or 25 - idx < 7 - cnt:
	return
	# 7명을 모두 소집한 경우
	if cnt == 7:
	visited = [[False for _ in range(5)] for _ in range(5)]
	visited[S[0]//5][S[0]%5] = True
	if check(S[0], visited, [1]):
	ans += 1
	return
	# 현재 인원의 위치
	r = idx // 5
	c = idx % 5
	# 현재 인원을 포함하는 경우
	S.append(idx)
	include[idx] = True
	# 현재 인원이 임도연파인경우
	if _map[r][c] == "Y":
	solve(idx+1, yn+1, cnt+1)
	# 현재 인원이 이다솜파인경우
	elif _map[r][c] == "S":
	solve(idx+1, yn, cnt+1)
	# 현재 인원을 포함하지 않는경우
	S.pop()
	include[idx] = False
	solve(idx+1, yn, cnt)
	def check(n, visited, cnt):
	if cnt[0] == 7:
	return True
	r = n // 5
	c = n % 5
	res = False
	for i in range(4):
	nr, nc = r + dr[i], c + dc[i]
	if 0<=nr<5 and 0<=nc<5 and not visited[nr][nc]:
	if include[nr*5+nc]:
	visited[nr][nc] = True
	cnt[0] += 1
	res = check(nr*5+nc, visited, cnt)
	if res:
	return res
	return res
	solve(0, 0, 0)
	print(ans)

view raw BOJ1941.py hosted with ❤ by GitHub