백준 21736 : 헌내기는 친구가 필요해

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

문제

1 2 3

풀이

DFS

Step 1 : Moving Offset

  • offset 배열을 선언하여 x, y 좌표가 움직이는 방향을 상하좌우로 설정한다.
  • move 함수를 x, y 좌표가 상하좌우 네 방향 중 하나를 입력받아 움직일 수 있도록 선언한다.

    Step 2 : DFS

  • 현재 좌표의 위치가 campus 내에 있고 아직 방문하지 않은 노드인 경우
    그 위치가 ‘P’라면 카운트 변수에 1을 더한다.
  • 상하좌우로 움직여 DFS를 재귀호출한다.

BFS

Step 1 : Moving Offset

  • offset 배열을 선언하여 x, y 좌표가 움직이는 방향을 상하좌우로 설정한다.
  • 이 경우에는 시간초과 문제로 move 함수를 따로 정의하진 않았다.

    Step 2 : BFS

  • 큐를 만들어 시작 좌표를 삽입한다.
  • 시작 좌표에서 상하좌우로 움직인 값을 p라고 가정했을 때, p값이 campus 안에 있고 아직 방문하지 않았다면
    ‘P’일 때 카운트 변수를 +1, ‘X’일 때는 방문했다고 표시한 후 큐에 p를 삽입한다.

댓글남기기

참고