순환 공간
https://koitp.org/problem/SDS_TEST_SPACE/read/
오답
BFS 로 풀었을 때는 메모리 초과가 뜬다.
해결
시뮬레이션으로 풀면 해결된다.
- 1번
- 돌아가지 않고 직접 가는 경우이다.
- 시작점과 도착점 사이의 절대값을 구한다.
- 2번
- 돌아가는 경우이다.
- 행과 열의 대소 비교를 통해 구한다.
마지막 생존자
https://koitp.org/problem/SDS_TEST_SURVIVOR/read/
풀이
이차원 배열을 순차탐색하여, 해당 index와 주변 8개의 값을 체크한다.
쉬운 문제인데, 오랜만에 알고리즘 문제를 푸니 오래걸렸다.
쉬어가는 페이지
https://koitp.org/problem/SDS_TEST_PAGE/read/
풀이
s에 j 를 더한 값이 쉬어 가는 page 인지 체크.
쉬운 문제인데, 오랜만에 알고리즘 문제를 푸니 오래걸렸다.
탈출
문제 요약
- 문자
- 비버 .
- 물 *
- 돌 X
- 비버굴 D
- 고슴도치 굴 S
- 매 분 1분 마다
- 고슴도치
- 동서남북으로 이동
- 돌을 통과할 수 없다
- 물
- 동서남북으로 이동
- 비어있는 칸으로 확장
- 비버의 소굴로 확장할수 없다
- 돌을 통과할 수 없다
- 고슴도치
풀이
- 이렇게 풀면 되지 않을까?
- 물의 확산 :DFS
- 고슴도치의 이동 :BFS
- 아니다 !
- BFS 만으로 풀 수 있다
- 물을 먼저 Enqueue
- 고슴도치의 위치를 Enqueue
- 하나의 큐에서 진행
Code
스타트링크
문제 요약
F층으로 이루어진 건물
스타트 링크는 G층
현재 위치 S층
U
- 위로 U층을 감
D
- 아래로 D층을 감
U층 위, 또는 D층 아래에 해당하는 층이 없을 때는,
- 엘리베이터는 움직이지 않는다
S층에서 G층 가려면 버튼을 적어도 몇번 눌러야해????
갈수 없다면 “use the stairs” 출력
풀이
- 전형적인 BFS
- 큐에서 deque를 한다 …. A
- 도착지점인지 확인한다.
- 도착 지점이면 끝
- 도착 지점이 아니라면 계속
- deque한 지점에서 이동 가능한 곳을 모두 큐에 넣는다
- 이동 가능 한 곳
- U층을 더 했을 때, 꼭대기 층 이하이어야함
- D층을 뺐을 때, 1층 이상이어야함
- 이동 가능 한 곳
- 다시 A부터 반복한다
촌수 계산
풀이
결국 최단 거리 문제. 따라서 BFS
테스트 케이스 대로 그래프를 그리면 다음과 같다
- 7에서 3까지의 최단 거리를 구하면 된다.
- 이는 곧 7에서 3까지의 depth를 구하는 것이다.
나이트의 이동
풀이
- 전형적인 BFS
- (1번) 큐에서 deque를 한다
- 도착지점인지 확인한다.
- 도착 지점이면 끝
- 도착 지점이 아니라면 계속
- deque한 지점에서 이동 가능한 곳을 모두 큐에 넣는다
- 다시 1번부터 반복한다
안전영역
https://www.acmicpc.net/problem/2468
풀이
비의 높이(지역 높이 최소~최대) 로 다음을 반복
- 물에 잠긴 영역 체크
- BFS로 안정 영역 개수 체크
오답 원인
최소 답을 0으로 설정하였기 때문에 계속 틀렸었다.
해결
최소 답은 1이다.
왜냐하면, 아무 것도 잠기지 않는다면 하나의 영역이기 때문이다.
숨바꼭질
풀이
https://www.acmicpc.net/problem/1697
- 현재 위치에서 이동 가능한 곳 체크
- X - 1
- X + 1
- X * 2
- 체크 조건
- 이동 가능한 곳이 범위 안에 있나?
- 아직 방문하지 않은 곳인가?
- Queue에서 이동 가능한 곳을 뽑아냄
- 동생의 위치이면 그래프의 Depth를 출력
- 그래프의 Depth를 표현하기 위해
- Class는 위치와 depth로 구성
팀배분
풀이
https://www.acmicpc.net/problem/1953
- 깊이에 따라 팀을 나눔
- 깊이 0, 2, 4, 6, 8 …. : 백팀
- 깊이 1, 3, 5, 7, 8 …. : 청팀
- 학생을 아직 방문하지 않았으면 학생을 root로 BFS
- 깊이 정보를 나타내기 위해 Student class 생성해서, 학생 번호와 깊이 저장