[BOJ] 1941 소문난 칠공주 바로가기
총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.
위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.
'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.
첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.
combinations()
함수를 통해 25C7 크기의 조합을 구한 후 해당 조합이 모두 연결되어 있는지 확인한 후 연결되어 있다면 해당 조합이 소문난 칠공주
를 결성할 수 있는지 탐색하는 방식을 이용하였다.백 트래킹(Back Tracking)
방법을 이용하여 문제를 해결할 수 있었다.cases = set()
def dfs(case, depth, cntY):
if cntY > 3:
return
if depth == 7:
cases.add(tuple(sorted(case)))
return
for x, y in case:
for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx, ny = x + dx, y + dy
if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
if table[ny][nx] == 'Y':
dfs(case + [(nx,ny)], depth + 1, cntY + 1)
else:
dfs(case + [(nx,ny)], depth + 1, cntY)
cntY
는 현재 조합(case
)에 존재하는 임도연파의 인원을 의미한다.cntY
의 값이 3 초과 즉, 7명 중 4명 이상인 과반수라면 해당 조합은 소문난 칠공주
에 해당하지 않으므로 진행을 멈춘다.if cntY > 3:
return
depth
는 현재 조합(case
)에 인원 수를 의미한다.depth
의 값이 7 즉, 소문난 칠공주
에 해당한다면 해당 조합(case
)은 '소문난 칠공주'를 저장할 집합 자료구조(cases
)에 저장한다.if depth == 7:
cases.add(tuple(sorted(case)))
return
case
)의 각 원소의 상하좌우 값에 해당하는 원소를 추가하여 다시 dfs
함수를 실행한다.case
)에 해당하거나 정사각형 격자에서 벗어난다면 해당 경우는 제외한다.if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
Y
)이라면 cntY
의 값을 1증가시켜서 dfs()
를 실행한다.if table[ny][nx] == 'Y':
dfs(case + [(nx,ny)], depth + 1, cntY + 1)
S
)이라면 depth
의 값만 1 증가시켜서 dfs()
를 실행한다.else:
dfs(case + [(nx,ny)], depth + 1, cntY)
for y in range(5):
for x in range(5):
if table[y][x] == 'S':
dfs([(x,y)], 1, 0)
x, y
)가 이다솜파 인원(S
)이라면 현재 위치값을 담은 배열(case
)은 [(x,y)]
의 값을, 현재 조합의 인원수(depth
)에는 1
의 값을, 현재 조합에 존재하는 임도연파의 인물 수(cntY
)에는 0
의 값을 할당하여 dfs()
를 실행한다.from sys import stdin
def solution(table):
cases = set() # ‘소문난 칠공주’ 결성 cases
def dfs(case, depth, cntY):
# 임도연파 학생이 과반수 이상일 경우
if cntY > 3:
return
# 7명의 구성이 완성되었을 경우
if depth == 7:
cases.add(tuple(sorted(case)))
return
# 모든 경우의 수를 탐색(dfs)
for x, y in case:
for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx, ny = x + dx, y + dy
if nx < 0 or nx > 4 or ny < 0 or ny > 4 or (nx,ny) in case: continue
if table[ny][nx] == 'Y':
dfs(case + [(nx,ny)], depth + 1, cntY + 1)
else:
dfs(case + [(nx,ny)], depth + 1, cntY)
for y in range(5):
for x in range(5):
if table[y][x] == 'S':
dfs([(x,y)], 1, 0)
return len(cases)
table = [list(stdin.readline().strip()) for _ in range(5)]
result = solution(table)
print(result)