[3주차_수요일] 18404_현명한 나이트

[Jewan1120]

• 사이트: 백준
• 문제: 현명한 나이트
• 번호: 18404번

[KodaHye]

🤔 시간복잡도 고려사항

• BFS로 풀이할 때 시간 복잡도
  • O(NN) (정점의 개수) × 8 (간선의 개수)
  • 1 <= N < 500, 1 <= M < 1,000
  • 500 × 500 × 8 < 1억

💡 풀이 아이디어

• 초기 나이트의 위치를 큐에 넣고 말을 다 잡을 때까지 진행하기
• Point 클래스
  • r, c: 좌표 위치
  • d: 움직인 거리
• int[][] map
  • 주어진 맵의 정보 저장
  • -1: 이미 방문한 곳
  • 0: 방문할 수 있는 곳
  • 1 ~ (M + 1): 말이 있는 곳
• int[] result
  • 말의 idx에 따라 거리가 얼마나 걸렸는지 저장

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000
• 500*1000 = 50,000
• BFS가능

💡 풀이 아이디어

• 전형적인 bfs문제
• 잡을 말 위치 별로 거리 출력하기
  • board에 말의 위치를 해당 말의 idx로 표기 (빈칸은 -1)
• 말 다 잡으면 bfs종료 (cnt로 관리)

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 500
• O(N^2) 가능 : BFS 가능

💡 풀이 아이디어

• Pos 객체를 선언해서 위치와 움직인 수 관리하기
• BFS로 상대의 말에 도달한 가장 빠른 움직인 수 기록
• 모든 상대편 말을 잡았다면 break

처음에 DFS로 풀었다가 멈추는 타이밍을 설정할 수 없어 시간초과가 발생했습니다,,, 최소거리 보장은 bfs ~ ^O^

[icegosimperson]

🤔 시간복잡도 고려사항

• N<=500, O(NN 1000) -> O(N^2)

💡 풀이 아이디어

• 각 상대편 말을 잡기 위한 나이트의 최소 이동 수 : BFS
• 처음에 나이트 경로를 지정 안하고, 방문 배열을 boolean으로 선언해서 헤맸습니다.
• 단순 방문만 체크하는 것이 아니라 나이트 최소 이동 횟수 구해야함 -> int 배열 선언

• 다른 분들 메모리, 시간을 보니 제가 유독 오래 걸렸어서 이 부분을 더 공부 해오겠습니다!

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 500 → O(N^2)의 BFS 가능

💡 풀이 아이디어

• BFS를 진행하면서 모든 좌표에 도착하는 최소 시간을 기록
• 상대방 말의 좌표를 순회하면서 해당 좌표의 최소 시간을 출력

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: bfs
• 시간복잡도: 1 ≤ N ≤ 500 체스판의 크기는 N*N 으로 최대 2500. O(N^2)까지 가능

💡 풀이 아이디어

• 나이트(K)는 8방향으로 움직일 수 있고, 말을 잡기 위한 최단거리를 구하는 문제 → BFS 알고리즘
• 각 8방향을 움직이는데, 현재 위치 ~ 다음 위치까지 이동한 거리를 각 위치마다 저장 체스판에도 이동거리 저장
• 체스판의 위치마다 이동한 거리를 계속해서 누적해서 저장하기 때문에 적(E)이 있는 위치가 최단거리가 됨