문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
1941번: 소문난 칠공주 문제 보러 가기
문제
총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.
위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.
- 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
- 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
- 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
- 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력
'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.
출력
첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.
예제 입력 1
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY
예제 출력 1
2
정말 어려운 문제였다. 또 대기업 코테에서 선호할거 같다. DFS와 BFS가 같이있는 백트래킹 문제...
L==7, 7명을 뽑을 때까지 25명을 반복문으로 확인한다.
이때 NxN 이자 5x5니깐 i번째 학생의 위치의 행은 총 25명중 i를 5로 나눈 값과 같고 열은 i를 5로 나눈 나머지와 같다.
res는 0번째 부터 6번째학생의 위치를 담는다. 현재 row, col 위치에서 임도연파 학생이면 임도연파 학생수 cnt를 증가시키고 깊이 L(1명을 뽑았으니깐)과 다음번째 학생을 보기위해 i+1을 한다.
임도연파 학생이 아니면 임도연파 학생수 cnt는 증가시키지 않고 다음 DFS를 진행한다.
다음 L==7이 되어 조건을(상하좌우 붙어있는지를) 확인하기 위해 BFS를 수행한다.
현재 학생의 상하좌우를 보며 범위안에 있고 다음학생을 처음 방문하는 경우 check를 +1 늘린다. 그리고 check가 7이 되면 7명 모두 인접하게 붙어있다는 뜻으로 True를 return 한다.
정답
import sys
from collections import deque
dr=[-1,0,1,0]
dc=[0,-1,0,1]
def BFS(princesses):
visited=[[1]*5 for _ in range(5)]
for r,c in princesses:
visited[r][c]=0 # 뽑은 7명의 학생들은 0으로 초기화
Q=deque()
Q.append(princesses[0]) # 뽑은 첫번째 학생부터 보자
visited[princesses[0][0]][princesses[0][1]]=1 # 첫 공주의 row, col은 방문한거로 체크
check=1 # 공주들 리스트가 7명이 맞는지 확인하기 위해
while Q:
r,c=Q.popleft()
for i in range(4): # 상하좌우 살피기
nr=r+dr[i]
nc=c+dc[i]
if 0<=nr<5 and 0<=nc<5 and visited[nr][nc]==0: # 범위안에서 다음 위치 첫방문
visited[nr][nc]=1
check+=1
Q.append((nr,nc))
if check!=7:
return False # 7명 모두 인접하지 않으면 False
else:
return True # 7명 모두 인접했으면 True
def DFS(L,s,cnt):
global ans
if cnt>=4: # 만약 임도연파가 4명이상이면
return # 볼것도 없이 재귀 탈출
if L==7: # 7명 모두 뽑음
if BFS(res): # res는 뽑은 7명 리스트, res가 모두 붙어 있으면 (조건에 만족하면)
ans+=1 # 경우의 수 +1 추가
else:
for i in range(s,25): # 5x5=25번을 돈다
row=i//5 # 총 25번 중 행은 i를 5로 나눈 값과 같다
col=i%5 # 총 25번 중 열은 i를 5로 나눈 나머지와 같다
res[L]=[row,col] # 해당 위치 추가
if board[row][col]=='Y': # # 임도연파 출신 공주가 있으면 cnt 증가
DFS(L+1,i+1,cnt+1)
else:
DFS(L+1,i+1,cnt)
if __name__=="__main__":
board=[list(map(str, input())) for _ in range(5)]
ans=0
res=[[0,0]]*7
DFS(0,0,0) # L=깊이(7명), s는 중복방지 및 증가, cnt는 임도연파 출신 공주수
print(ans)
