Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 시뮬레이션
- 트리
- 해시
- DFS
- MST
- 다시
- 투포인터
- DP
- BFS
- 다이나믹 프로그래밍
- 백트래킹
- 재귀
- 구현
- 플로이드-워셜
- 그래프 이론
- 그래프 탐색
- 자료구조
- 다익스트라
- 다이나믹프로그래밍
- 에라토스테네스의 체
- 수학
- join
- 서브쿼리
- 우선순위큐
- 브루트포스
- GROUP BY
- 누적합
- 그리디
- 크루스칼
- 분할정복
Archives
- Today
- Total
기록하고 까먹지 말기
2210 본문
날짜 : 2023. 03. 08
사용 언어 : python
문제
코드
import sys
sys.setrecursionlimit(10**6)
a = list() # 5 x 5 숫자판
num = dict()
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(r, c, n):
if len(str(n)) == 6:
#print(n)
if n not in num:
num[n] = 1 # 해당 수가 없는 경우 해시에 추가
return
for i in range(4):
x = r + dx[i]
y = c + dy[i]
if x in range(5) and y in range(5):
dfs(x, y, str(n) + str(a[x][y]))
return
for _ in range(5):
a.append(list(map(int, sys.stdin.readline().split()))) # 숫자판 입력
for i in range(5):
for j in range(5):
dfs(i, j, a[i][j])
#print(num.keys())
print(len(num.keys()))
풀이
- 숫자판에 대해 DFS를 활용하여 탐색하면서 해시를 사용해 길이에 도달한 숫자 여부를 확인 후 추가한다.
- 지나갔던 지점을 다시 지나갈 수 있기 때문에 인접노드 경우의 수를 모두 넣어서 탐색한다.
알게된 점
-
참고 사이트
-