[ BOJ / Python ] 1941번 소문난 칠공주

황승환·2022년 4월 30일
0

Python

목록 보기
285/498


이번 문제는 백트레킹을 통해 가능한 좌표들의 조합을 구하고, 해당 조합을 순회하며 연결되어 있는지 DFS를 통해 확인하도록 하였다. 조합을 구할 때에는 조합 하나가 완성 되었을 때, S가 4개 이상 존재하지 않으면 추가하지 않도록 하여 갯수를 줄였다.

Code

grid=[list(str(input())) for _ in range(5)]
answer=0
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
idxs=[(i, j) for i in range(5) for j in range(5)]
combs=[]
cnt=0
def get_combs(cur, comb):
    if cur==len(idxs):
        if len(comb)==7:
            if get_chk(comb):
                combs.append(comb)
        return
    if len(comb)>7:
        return
    get_combs(cur+1, comb+[idxs[cur]])
    get_combs(cur+1, comb)
def get_chk(comb):
    result=0
    for y, x in comb:
        if grid[y][x]=='S':
            result+=1
    return result>=4
def get_connect(y, x, comb):
    global cnt
    for i in range(4):
        ny, nx=y+dy[i], x+dx[i]
        if 0<=ny<5 and 0<=nx<5 and not visited[ny][nx] and (ny, nx) in set(comb):
            visited[ny][nx]=True
            cnt+=1
            get_connect(ny, nx, comb)
get_combs(0, [])
for comb in combs:
    cnt=0
    visited = [[False for _ in range(5)] for _ in range(5)]
    visited[comb[0][0]][comb[0][1]]=True
    get_connect(comb[0][0], comb[0][1], comb)
    if cnt==6:
        answer+=1
print(answer)

profile
꾸준함을 꿈꾸는 SW 전공 학부생의 개발 일기

0개의 댓글