728x90
반응형
https://www.acmicpc.net/problem/1941
1941번: 소문난 칠공주
총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작
www.acmicpc.net
문제해결
- 조건이 4가지를 만족해야하므로 차례대로 만족시킬 수 있는 방법이 뭔지 생각해본다.
- 1번과2번조건을 묶고 3번과 4번 조건을 묶으면 좋다.
- 7명의 여학생으로 구성되어있어야하므로 depth=7인 dfs를 사용하면 좋을 것 같다. (게다가 가로 또는 세로로 인접해 있어야하므로 dfs로 이동하는 것은 좋다.)
- 임도연파가 4명 이상이면 안되는 것이기 때문에 중간에 그만두고 다른 것을 찾도록 한다.
- bfs를 통해 가로 또는 세로로 이동해서 모두 연결할 수 있는지 확인한다.
- 가능하면 정답변수 result +1 을 해준다.
CODE
from collections import deque
def bfs(arr):
dr = [-1,+1,0,0]
dc = [0,0,-1,+1]
visited = [[1]*5 for _ in range(5)]
for i in A:
visited[i[0]][i[1]] = 0
queue = deque([A[0]])
visited[A[0][0]][A[0][1]] = 1
check = 1
while queue:
r, c = queue.popleft()
for ur, uc in zip(dr,dc):
nr = r + ur
nc = c + uc
if 0<=nr<5 and 0<=nc<5:
if not visited[nr][nc]:
visited[nr][nc] = 1
check += 1
queue.append((nr,nc))
if check != 7:
return False
else:
return True
def dfs(depth, start, count):
global result
if count >= 4: # 임도연파가 4명보다 많으면 중간에 early stopping
return
if depth ==7:
if bfs(A):
result += 1
return
for i in range(start, 25):
r = i//5
c = i%5
A.append((r,c))
dfs(depth+1, i+1, count+(seats[r][c] =='Y')) # 임도연파면 count+1 이다솜파면 count
A.pop()
if __name__=='__main__':
seats = [[str(c) for c in input().rstrip()] for _ in range(5)]
A = []
result = 0
dfs(0,0,0)
print(result)
728x90
반응형
'알고리즘 > [python] 백준 BOJ' 카테고리의 다른 글
[python] 백준 1799 비숍 (0) | 2023.04.20 |
---|---|
[python] 백준 16987 계란으로 계란치기 (0) | 2023.04.18 |
[python] 백준 2482 색상환 (0) | 2023.04.18 |
[python] 백준 1788 피보나치 수의 확장 (0) | 2023.04.17 |
[python] 백준 2240 자두나무 (0) | 2023.04.17 |
댓글