탐색 - visited variation

문제 번호는 문제 링크, 제목은 풀이 링크

• search - visited
  
  • visited가 필요하지 않은 경우
    • 한 방향으로만 탐색해서 왔던 길을 되돌아갈 수 없는 경우
      • 백준 17070 파이프 옮기기 1
      • SWEA 1949 등산로 조성
  • 작은 visited만 필요한 경우
    • SWEA 1949 등산로 조성 (높이 9)
  • 큰 visited가 필요한 경우 -> representation, 자료구조 고민
    • 백준 1525 퍼즐
  • visited 추가 차원이 필요할 경우
    • BFS(최소 거리) : 첫번째 방문한 자손만 유효하기 때문에 자손간 visited 공유 가능
      • 특정 지점 N개에서 탐색 조건이 바뀌는 경우([1>>N])
        • 백준 1194 달이 차오른다, 가자 (열쇠 획득 전후 상응하는 문을 향하는 것은 다른 의미)
        • 백준 17244 아맞다우산 (물건 획득 전후 탐색은 다른 의미)
        • 백준 1559 놀라운 미로 (물건 획득 전후 탐색은 다른 의미)
      • 특정 회수(N)만큼 탐색 조건을 바꿀 수 있는 경우([N])
        
        • 백준 2206 벽 부수고 이동하기 (벽 부순 횟수만큼)
      • 특정 시점(T)에 탐색 조건이 바뀌는 경우([T])
        • 백준 16954 움직이는 미로 탈출 (미로 움직인 횟수만큼)
      • 특정 지점에 여러가지 상태 N개로 존재하는 경우([N])
        • 백준 1938 통나무 옮기기(각 칸에서 가로, 세로로 존재 가능)
        • 백준 1726 로봇 (각 칸에서 4가지 방향을 바라볼 수 있음)
        • 백준 1559 놀라운 미로 (4를 주기로 문이 열리는 방향이 바뀜)
      • 기타
        • 백준 15558 점프게임
        • 백준 17071 숨바꼭질 5
    • DFS(최대 거리) : 자손간 visited 공유 불가능(분기 때마다 새로운 v 사용하거나 visited 복구 필요), return 전후에 visited = 0 처리
      • 특정 회수만큼 탐색 조건을 바꿀 수 있는 경우
        • SWEA 1959 등산로 조성 (분기만큼)
        • 백준 13459 구슬 탈출 1, 2, 3, 4
  • visited 추가 차원이 2개 필요한 경우
    • 백준 1559 놀라운 미로
• search - 비용이 상하좌우 이동이 아닌 경우
  • 백준 9376 탈옥

• 기타 점층 처리
  • SWEA 디저트 카페
  • 백준 two dots