[BOJ 1941] 소문난 칠공주

문제

[BOJ 1941] 소문난 칠공주

시도1

코드

import sys

input = sys.stdin.readline

board = []
for _ in range(5):
    board.append(list(input().rstrip()))
   
for i in range(5):
    print(board[i])
    
dx = [0,0,1,-1] # 동서남북
dy = [1,-1,0,0]  
    
def back(x,y,S,Y,cnt,visited,route):
    global answer
    if cnt==7:
        if S>Y:
            answer.add(tuple(route[:-1]))
        return
    
    if x<0 or x>=5 or y<0 or y>=5: return
    if visited[x][y]: return
    
    if board[x][y]=='S':
        S += 1
    elif board[x][y]=='Y':
        Y += 1
    
    visited[x][y]=True
   
    for dir in range(4):
        nx,ny = x+dx[dir],y+dy[dir]
        route.append((nx,ny))
        back(nx,ny,S,Y,cnt+1,visited,route[:])
        route.pop()
        

answer = set()
for i in range(5):
    for j in range(5):
        visited = [ [False]*5 for _ in range(5) ]
        back(i,j,0,0,0,visited,[(i,j)])
        
print(len(answer))

문제점

케이스1   케이스2
.....    .....
SYSYS    SYSYS
....Y    .Y...
....S    .S...
.....    .....

케이스2에서 (2,1)일 때 SYSYS까지 갔던 걸 기억 못하고 cnt=1,S=1,Y=1이 됨

시도2

1. 백트래킹에서 현재 person에 대해서만 조사하는 게 아니라 모든 people에 대해 조사함
2. 임도연파가 4명 이상이면 가지치기(파이썬 자료형을 적극 활용함)

import sys
input = sys.stdin.readline

board = []
for _ in range(5):
    board.append(list(input().rstrip()))
    
answer = dict()

dx = [0,0,1,-1] # 동서남북
dy = [1,-1,0,0]

def back(people):
    
    global answer
    
    # 임도연파가 4명 이상이면 가지치기(파이썬 자료형 적극 활용)
    if ''.join([board[p//5][p%5] for p in people]).count('Y')>3: return
    
    # 7명이 되면 answer에 중복된 people이 있는지 확인
    if len(people)==7:
        people = ''.join(map(str,sorted(people)))
        if people not in answer:
            answer[people] = 1
        return
      
    ### 핵심 !! 칠공주에 들어간 모든 사람들에 대해 다시 조사
    for person in people:
        x,y = person//5,person%5
        for dir in range(4):
            nx,ny = x+dx[dir],y+dy[dir]
            if nx<0 or nx>=5 or ny<0 or ny>=5: continue
            adj = nx*5+ny
            if adj not in people:
                people.append(adj)
                back(people[:])
                people.pop() 
                
for person in range(25):
    back([person])
    
print(len(answer.keys()))

시도3 (가지치기)

해당 번호의 사람이 속하는 칠공주 그룹 구했는지 체크하는 check배열 만들기
그럼 back에서 탐색할 때 가지치기 할 수 있음(check==True면 이미 만들어진 그룹이라는 거니까)

import sys
input = sys.stdin.readline

board = []
for _ in range(5):
    board.append(list(input().rstrip()))
    
answer = dict()

dx = [0,0,1,-1] # 동서남북
dy = [1,-1,0,0]

def back(people):
    
    global answer,check
    
    # 임도연파가 4명 이상이면 가지치기
    if ''.join([board[p//5][p%5] for p in people]).count('Y')>3: return
    
    # 7명이 되면 answer에 중복된 people이 있는지 확인
    if len(people)==7:
        people = ''.join(map(str,sorted(people)))
        if people not in answer:
            answer[people] = 1
        return
      
    # 그룹의 모든 사람에 대하여 백트래킹 해야함
    # 케이스2 같이 분기되는 경우도 다 고려해야하기 때문
    for person in people:
        x,y = person//5,person%5
        for dir in range(4):
            nx,ny = x+dx[dir],y+dy[dir]
            if nx<0 or nx>=5 or ny<0 or ny>=5: continue
            # check[nxtperson]==True면 이미 만들어진 그룹(가지치기)
            nxtperson = nx*5+ny
            if check[nxtperson]: continue
            if nxtperson not in people:
                people.append(nxtperson)
                back(people[:])
                people.pop() 

# 해당 번호의 사람이 속하는 칠공주 그룹 구했는지 체크용           
check = [False]*25               
for person in range(25):
    x,y = person//5,person%5
    # 이다솜파 한명이 속하는 칠공주 그룹 모두 구하기
    if board[x][y]=='S':
        check[person]=True
        back([person])
    
print(len(answer.keys()))