https://www.acmicpc.net/problem/1941
조합,순열,백트래킹 문제
divmod라는 함수로 1차원 인덱스를 2차원 좌표로 만들어주면
편하게 접근이 가능하다.
selected[i]는 i번째 선택된 칸의 좌표 (x,y) 튜플을 의미한다.
import sys,math
from collections import deque
input= sys.stdin.readline
li=[]
for _ in range(5):
str_line= input().rstrip()
li.append(list(str_line))
ans=0
def check(str):
cnt=0
for i in str:
if i=='S':
cnt+=1
return cnt>=4
def isconnected(selected):
q=deque()
q.append(0)
visit=[False] *[7]
visit[0]=True
cnt=1
while q:
cur = q.popleft()
curX,curY=selected[cur]
for i in range(1,7):
if not visit[i]:
tarX,tarY=selected[i]
if abs(curX-tarX) + abs(curY-tarY)==1:
visit[i]=True
q.append(i)
cnt+=1
return cnt==7
def dfs(idx,cnt,str,selected):
global ans
if cnt==7:
if check(str) and isconnected(selected):
ans+=1
return
for i in range(idx,25):
r,c=divmod(i,5)
selected[cnt]=(r,c)
dfs(i+1,cnt+1,str+li[r][c],selected)
selected = [0] * 7
dfs(0,0,"",selected)
print(ans)'크래프톤정글10기 > 파이썬' 카테고리의 다른 글
| [백준/G2] 가운데를 말해요 (0) | 2025.08.22 |
|---|---|
| [백준/G4] 스도쿠 (1) | 2025.08.18 |
| DP + 그리디 과제 정리 (4) | 2025.08.06 |
| 파이썬으로 이해하는 트리,그래프 (3) | 2025.07.25 |
| 0712: 파이썬 알고리즘 (0) | 2025.07.12 |