Recent Posts
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 | 31 |
Tags
- table not found
- 달인막창
- 코루틴 컨텍스트
- VARCHAR (1)
- 티스토리챌린지
- JanusGateway
- k8s #kubernetes #쿠버네티스
- PersistenceContext
- PytestPluginManager
- python
- tolerated
- terminal
- 겨울 부산
- Value too long for column
- 개성국밥
- 헥사고날아키텍처 #육각형아키텍처 #유스케이스
- JanusWebRTCServer
- 깡돼후
- 코루틴 빌더
- 오블완
- kotlin
- Spring Batch
- pytest
- vfr video
- JanusWebRTC
- mp4fpsmod
- preemption #
- 자원부족
- taint
- JanusWebRTCGateway
Archives
너와 나의 스토리
(BOJ) 1941 소문난 칠공주 (테스트케이스有) 본문
반응형
문제: https://www.acmicpc.net/problem/1941
문제 풀이:
* 처음에는 단순하게 dfs로 풀었는데
|
|
ㅇ |
|
|
ㅇ |
ㅇ |
ㅇ |
ㅇ |
ㅇ |
|
|
ㅇ |
|
|
이런식으로 이동이 불가능 했다 -> fail
- 무작위로 7명을 뽑아낸 후
- '이다솜파(S)'가 더 많은지 (4명 이상) 확인
YES -> 모두 연결되어 있는가 (bfs 이용)
YES -> cnt++;
소스 코드:
https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1941
Testcase:
case1:
YYYYY
YYSYY
YSYSY
YYSYY
YYYYY
-> 답1: 48
case2:
YYYYY
YYSYY
YSSSY
YYSYY
YYYYY
-> 답1: 592
* 다른 방법: 훨씬 빠름
bfs, dfs 둘 다 가능
직전 위치에서만 이동하는 것이 아니라
지금껏 이동한 (state로 기록된) 곳 아무 곳에서나 상하좌우로 이동
반응형
'Algorithm > 백트래킹 (Backtracking)' 카테고리의 다른 글
| [BOJ] 1987 알파벳 (0) | 2020.05.08 |
|---|---|
| (BOJ) 3109 빵집 (0) | 2019.02.02 |
| (BOJ) 2210 숫자판 점프 (0) | 2019.02.01 |
| (BOJ) 1339 단어수학 (0) | 2019.02.01 |
| (BOJ) 2023 신기한 소수 (0) | 2019.02.01 |
Comments