프린터 큐

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

      ….

Read more

연구소

풀이

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

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

로봇청소기

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 에서 구할 수 있다.
Read more