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번부터 반복한다