풀이

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

• 트리의 깊이가 얼마인지 구하면 됨
  • 현재위치에서 갈 수 있는 곳을 Queue에 넣을 때,
  • 위치와 트리의 depth를 함께 저장한다.
  • 위치
    • 8가지 경우의 수
  • 트리의 depth
    • 현재위치의 깊이+1

풀이

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

• 경우의 수

  • A -> B
  • A -> C
  • B -> A
  • B -> C
  • C -> A
  • C -> B

• 가능한 모든 경우를 Queue에 넣어가면서 체크

• EX

  • (0 0 10)

  • (8 0 2), (0 9 1)

    • (0 8 2), (0, 0, 10) : 이미 체크했으므로 큐에 넣지 않음, (8, 2, 0)
    • (8 1 1), (0 0 10) : 이미 체크했으므로 큐에 넣지 않음, (1 9 0)

    ….

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++

풀이

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

• 가장 적은 종류
  • 따라서, BFS
• 한 너비를 끝 마치고 다음 너비로 이동
  • 이를 위해, 현 위치에서 갈 수 있는 곳들을 큐에 add

풀이

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

• 최소 횟수를 구한다
  • 따라서, BFS
• 현재 숫자에서 각 자리 수마다 하나씩 바꿈
  • 소수이면 큐에 넣음
• 한 너비씩 진행
• 최종 찾고자 나오면 바로 출력해도 됨
  • 한 너비에서 진행되고 있기 떄문에

풀이

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

1. 이차원 배열의 각 index에 순차적으로 접근

2. 양, 늑대 count

3. 현재 위치를 기준으로 상하좌우 조사

   • 울타리가 X && 방문 X
   • 이동

3. 2번 다시 수행