풀이 및 해설(주석)
import sys
# sys.stdin = open('칠공주.txt', 'r')
sys.setrecursionlimit(10**6)
# dfs와 bfs가 섞여서 사용됨
def solve(nums, S, Y):
global rst, visit
if Y > 3: return
# 중복 방지를 위해 7개의 글자의 좌표를 정렬해서 튜플로 묶어서 visit이란 set에 저장
if len(nums) == 7:
nums = tuple(sorted(nums))
if nums not in visit:
rst += 1
visit.add(nums)
return
return
# 여기서 부터가 bfs섞인 부분, nums에 넣어준 좌표들을 pop하면 안됨 그냥 읽으면 됨
for num in nums:
r, c = num[0], num[1]
for dr, dc in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N:
# 방문 여부를 확인하기 위한 작업, 그냥 nums안에 있으면 방문했던 곳임
if (nr, nc) not in nums:
if students[nr][nc] == 'Y':
solve(nums+[(nr, nc)], S, Y+1)
else:
solve(nums+[(nr, nc)], S+1, Y)
students = [list(map(str, input())) for _ in range(5)]
N = 5
visit = set()
rst = 0
for i in range(N):
for j in range(N):
if students[i][j] == 'S':
solve([(i, j)], 1, 0)
else:
solve([(i, j)], 0, 1)
print(rst)
후기 및 해설
- 처음 문제를 보고, dfs로 풀면 되겠다 라고 판단 -> 실패
- 이유: dfs는 크로스로 방문이 안됨.
0 1 0 0
0 1 1 1
0 1 0 0
0 1 0 0
- 이런 식으로는 탐색이 안됨.
- bfs를 사용하는데, dfs처럼 재귀를 이용
- solve함수는 nums: list (좌표들을 튜플로 저장), S (S의 수), Y (Y의 수)를 매개변수로 받음
- 가지치기 적당히 넣어주고, nums의 수가 7개면 이다솜파가 될 수 있는 학생들을 찾은거임
- 이때, 중복 방지위해 [(0, 1), (0, 2)...] 형태로 저장된 nums를 visit이란 set에 넣어주기 위해
- 먼저 정렬하고, 튜플로 변경하고 visit에 저장
- 어려운 문제였음..
