https://www.acmicpc.net/problem/1966

풀이

• queue에서 하나씩 dequeue하면서 우선순위가 더 큰 문서가 있는지 확인

  • 이를 위해, temp queue를 생성

• ex

  • original : 1 2 3 4

    • temp : 2 3 4 1
      • 우선순위 더 큰 문서가 있음

  • original : 2 3 4 1

    • temp : 3 4 1 2
      • 우선순위 더 큰 문서가 있음

  • original : 4 1 2 3

    • temp : 1 2 3 4
    • temp : 2 3 4 1
    • temp : 3 4 1 2
      • 우선순위 더 큰 문서가 없음
      • original 에서 head remove

  • original : 1 2 3

    ….

풀이

https://www.acmicpc.net/problem/1389

• 유저의 수 만큼 BFS
  • start(root) 에서 다음 유저까지 가는데 얼마나 가야하는지
    • depth 구하는것과 동일
      • queue에 넣을 때, 부모가 누구인지도 같이 저장하면 됨

풀이

https://www.acmicpc.net/problem/14502

• 반복
  • 벽 3개 설치 => DFS
    • 첫 번째 벽 어디 세울지 찾음 ( 첫번째 dfs 메소드 )
      • for문 다 돌면, main을 돌아가
    • 두 번째 벽 어디 세울지 찾음 ( 두 번째 dfs 메소드 )
      • for문 다 돌면, ( 첫번째 dfs 메소드 )로 돌아가
    • 세 번째 벽 어디 세울지 찾음 ( 세 번째 dfs 메소드 )
      • 세우고, 바이러스 퍼뜨림
      • 세번째 벽 세웠던거 초기화하고
      • ( 두 번째 dfs 메소드 ) 로 돌아감
  • 바이러스 퍼짐 => BFS
  • 0의 개수 세기
• 0의 개수의 최댓값 구하기

https://www.acmicpc.net/problem/4991

다시 푼 문제이다. 어떻게 풀어야하는지 전혀 감이 잡히지 않았다. 해설을 보고 이해를 하였다.

풀이

1. map 입력을 받으며, 더러운 칸이면 칸의 위치를 백터에 저장한다.
2. 시작 위치에서 더러운 칸을 이동하는 최소값을 next_permutation()을 이용하여 구한다.

예시

• 다음과 같이 더러운 칸이 세 곳 이라고 하자.
  • Start Point
  • Dirty Point 01
  • Dirty Point 02
  • Dirty Point 03
• 방문하는 순서는 다음과 같은 경우들이 있다. 이 때, next_permutation() 을 이용한다.
  • S -> 01 -> 02 -> 03
  • S -> 01 -> 03 -> 02
  • S -> 02 -> 01 -> 03
  • S -> 02 -> 03 -> 01
  • S -> 03 -> 01 -> 02
  • S -> 03 -> 02 -> 01
• 그렇다면 이동 경로 거리는 어떻게 구할까? 위 예시 중, 가장 위의 경우를 보자.
  • S -> 01 최단 거리 : S를 시작점으로 하는 BFS 에서 구할 수 있다.
  • 01 -> 02 최단 거리 : 01을 시작점으로 하는 BFS 에서 구할 수 있다.
  • 02 -> 03 최단 거리 : 02를 시작점으로 하는 BFS 에서 구할 수 있다.

풀이

https://www.acmicpc.net/problem/2606

• 1번 컴퓨터와 연결된 컴퓨터를 차례대로 최대한 깊게 방문
  • DFS
• 컴퓨터 방문할 때마다 ans++