총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.
위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력
'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.
출력
첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.
각 자리에 0부터 24까지의 번호가 부여된다.
(0, 0)은 0번, (0, 1)은 1번, ... (4, 4)는 24번으로,
i번 자리의 x좌표는 i / 5, y좌표는 i % 5의 값을 갖는다.
또한, (x, y) 좌표의 번호는 (x*5 + y)번 이다.
각 자리의 방문 여부는 비트로 체크한다.
path라는 변수에 현재 경로를 저장하고, visited 배열에 해당 경로를 방문한 적 있는지 체크한다.
현재 경로에 있는 모든 지점에 대해 인접한 방향을 검사한다.
인접한 위치가 현재 경로에 포함되어 있지 않고 해당 경로를 탐색한 적 없다면 dfs로 다음 위치를 탐색한다.
임도연파(yy)가 4명 이상이 되면 return하고, 학생 수(ss+yy)가 7명이 되면 cnt를 증가시킨다.
N = 7
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]
board = list(list(input()) for _ in range(5))
visited = [0 for _ in range(1<<25)] # 경로 방문 체크
cnt = 0
def dfs(path, ss, yy): # 경로, 이다솜파, 임도연파
global cnt
if yy >= 4: return
if ss + yy == N:
cnt += 1
return
for node in range(25): # 현재 경로에 속한 모든 노드를 검사
if (not path & (1<<node)): continue
x, y = int(node / 5), int(node % 5) # 현재 위치
for d in range(4):
nx, ny = x + dxy[d][0], y + dxy[d][1] # 인접 위치
if nx < 0 or nx >= 5 or ny < 0 or ny >= 5: continue
num = nx * 5 + ny # 인접 위치의 번호
if visited[path|(1<<num)]: continue # 방문한 적 있는 경로인지 체크
visited[path|(1<<num)] = 1
if board[nx][ny] == 'S':
dfs(path|(1<<num), ss+1, yy)
else:
dfs(path|(1<<num), ss, yy+1)
# 0부터 25개의 자리에서 탐색 시작
for i in range(5):
for j in range(5):
num = i * 5 + j
visited[1<<num] = 1
if board[i][j] == 'S':
dfs(1<<num, 1, 0)
else:
dfs(1<<num, 0, 1)
print(cnt)