[백준]1941 소문난칠공주

1.풀이

[백준]1035 조각움직이기 (https://sosoeasy.tistory.com/39) 와 비슷한 문제이다.

(1) 모든 경우의 수를 조합으로 구한다

(2) (1)에서 구한 경우가 임도연파(Y)가 4명이상인지 확인한다.

(3) 4명이상이면 bfs를 통해서 연결되어있는지 확인한다.

- 소스코드1 : dfs를 이용하여 연결여부 확인

- 소스코드2 : bfs를 이용하여 연결여부 확인 -> 내생각엔 이게 더 쉽다.

 

* 이런류의 문제를 백트래킹으로 생각하면 조건 처리가 힘들어지는 경우가 많다. 완전탐색으로 보이는 문제는 깔끔하게 순열, 조합으로 풀 수 없을까 고민하는 자세가 필요하다.

 

2. 소스코드

(1) 소스코드1 (dfs를 이용)

from itertools import combinations

dR=[0,0,-1,1]
dC=[1,-1,0,0]
comb=list(combinations([i for i in range(25)],7))
L=[]
for i in range(5):
    L.append(input())


def cntY(loc):
    cnt=0
    for i in range(7):
        r=loc[i][0]
        c=loc[i][1]
        if L[r][c]=="Y":
            cnt+=1
    return cnt

def dfs(r,c):
    global cnt
    for k in range(4):
        tempR=r+dR[k]
        tempC=c+dC[k]
        if 0<=tempR<5 and 0<=tempC<5 and temp[tempR][tempC]==1 and visited[tempR][tempC]==0:
            cnt+=1
            visited[tempR][tempC]=1
            dfs(tempR,tempC)



ans=0
for com in comb:
    loc=[]
    for i in range(7):
        r=com[i]//5
        c=com[i]%5
        loc.append([r,c])
    # 네명 이하면 붙어있는지 확인
    if cntY(loc)<4:
        cnt=1
        temp = [[0 for j in range(5)] for i in range(5)]
        visited = [[0 for j in range(5)] for i in range(5)]
        for r,c in loc:
            temp[r][c]=1
        visited[loc[0][0]][loc[0][1]]=1
        dfs(loc[0][0],loc[0][1])

        if cnt==7:
            ans+=1

print(ans)

 

(2) 소스코드2 (bfs를 이용)

from itertools import combinations
from collections import deque

dR=[0,0,-1,1]
dC=[1,-1,0,0]
comb=list(combinations([i for i in range(25)],7))
L=[]
for i in range(5):
    L.append(input())


def cntY(loc):
    cnt=0
    for i in range(7):
        r=loc[i][0]
        c=loc[i][1]
        if L[r][c]=="Y":
            cnt+=1
    return cnt

ans=0
for com in comb:
    loc=[]
    for i in range(7):
        r=com[i]//5
        c=com[i]%5
        loc.append([r,c])
    # 네명 이하면 붙어있는지 확인
    if cntY(loc)<4:
        visited = [[0 for j in range(5)] for i in range(5)]
        tempL = [[0 for j in range(5)] for i in range(5)]
        for r,c in loc:
            tempL[r][c]=1

        visited[loc[0][0]][loc[0][1]]=1
        q=deque([loc[0]])
        cnt=1
        while(q):
            r,c=q.popleft()
            for k in range(4):
                tempR=r+dR[k]
                tempC=c+dC[k]
                if 0<=tempR<5 and 0<=tempC<5 and visited[tempR][tempC]==0 and tempL[tempR][tempC]==1:
                    cnt+=1
                    q.append([tempR,tempC])
                    visited[tempR][tempC]=1

        if cnt==7:
            ans+=1
print(ans)