[9주차_월요일] 전투 로봇

[Jewan1120]

• 사이트 : 코드트리(CT)
• 문제: 전투 로봇
• 년도: 2018

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= 행, 열의 크기 <= 20
• BFS로 풀이한다면 20 * 20 * 4 * (20 * 20 - 1) < 1억이므로 시간 충분함!

💡 풀이 아이디어

• 전투로봇의 이동 규칙에 의해 우선순위 큐를 사용한 BFS로 문제풀이
• Point: 행, 열을 저장
• qPoint: 우선순위 큐에서 사용할 정보 저장Point, d: 거리(시간)
• int[][] levelMap: 로봇, 몬스터 레벨에 대한 정보 저장
• int[][] monsterIdxMap: 몬스터의 위치를 idx를 통해 저장
• bfs()
  • 로봇의 위치를 기준으로 너비우선탐색을 하며 없앨 수 있는 몬스터 정보 구하기
  • 몬스터를 없앨 수 있다면
    • dieMonsterCnt 과, robotLevel 증가시키기
    • levelMap과 monsterIdxMap에서 제거된 몬스터의 정보 없애기
    • 로봇의 위치를 제거된 몬스터의 위치로 바꿔주기

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 20

=> 몬스터 탐색 : 최대 몬스터 수 O(N N - 1) => bfs탐색: O(NN) => 총 O(N N (N * N - 1)) 으로 완전탐색 가능

💡 풀이 아이디어

• g : 몬스터들의 레벨이 포함된 그래프
• 전투 로봇의 위치를 따로 저장하기 : Pos robot = new Pos(i, j, 2)
• bfs 탐색으로 없앨 수 있는 가장 가까운 몬스터 찾기
  • 큐로 로봇이 갈 수 있는 모든 몬스터를 탐색하고 우선순위 큐를 이용하여 가장 적합한 몬스터 출력
  • 가장 적합한 몬스터를 찾지 못했다면 작업 중단
  • 찾았다면, 해당 몬스터 없애고 로봇의 위치 변경
• 찾은 몬스터 수가 현재 레벨과 같다면 레벨 증가 && 찾은 몬스터 수 0으로 초기화

몬스터 찾기 우선순위를 {상하좌우} or {상좌하우} 이렇게 방향 탐색으로만 정하려고 했는데 오답이 나와서 그냥 우선순위큐로 문제에서 원하는 대로 우선순위를 설정했습니다 ㅎㅎㅎ 삼성 문제를 풀때 방향에 대한 우선순위가 주어지면 우선순위큐로 해야하는지, 방향 탐색으로만 가능한지 항상 헷갈리는 것 같습니다,,,, ㅎㅎㅎ

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 20
• 완전탐색 가능

💡 풀이 아이디어

• 더 이상 몬스터를 잡지 못할때까지 진행
  • 첫번째 while문 종료 조건: if (!isCatch) break;
• bfs 수행하면서 몬스터 잡기 (두번째 while문)
  • 현재 위치에서 몬스터 잡을 수 있다면
    • 몬스터 잡고 위치 업데이트
    • 두번째 while문 탈출
  • 현재 위치에서 몬스터 못 잡으면
    • 다음 방향으로 이동
    • 이때 우선순위큐에 다음 좌표 넣어서 조건에 맞는 다음 값이 나올 수 있도록 함
• 두번째 while문 탈출 후
  • 몬스터를 잡았으면 레벨체크 후 계속 진행
  • 몬스터 못잡았으면 끝

문제이해 올바르게하고 설계하기! 시뮬레이션 문제는 너무 객체객체하게 생각하지 말기,,, 구현 더 복잡해지기만 함,,,

[icegosimperson]

🤔 시간복잡도 고려사항

2 ≤ n ≤ 20 BFS 탐색 O(N N) 몬스터 수(N * N -1) -> 완전 탐색 가능

💡 풀이 아이디어

• 문제에서 구하는 것 : 전투로봇이 일을 끝내기 전까지 걸린 시간을 출력
  • 조건 : 로봇의 레벨은 2로 시작, 자신의 레벨보다 낮은 몬스터만 제거O, 레벨이 같은 몬스터는 지나갈 수 있지만 제거X
  • 잡을 몬스터 찾기(BFS) + 우선 순위큐로 타겟 선정에 따른 정렬 : (compareTo)
• Node 객체 선언(x좌표, y좌표, d거리)
  • d까지 선언한 이유 : 최단 거리 기준으로 잡을 몬스터를 선택 -> 최단거리 추적 필요
• 전투 로봇의 위치를 저장하고 위치 초기화
• List<Node> temp : 잡을 수 있는 몬스터를 저장하는 리스트
• 잡을 몬스터가 여럿일 경우 우선순위가 있기에 우선순위에 따라 정렬
• 잡을 몬스터(target)를 찾음 -> 전투 로봇 이동 -> 잡은 몬스터 수++ -> 로봇의 레벨++

정렬하는게 어려웠습니다...!! BFS 구현 연습도 많이 많이 하기....

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: BFS + 구현
• 시간복잡도: 2 ≤ n ≤ 20 BFS 탐색을 통해 각 로봇마다 최단거리를 구할 경우 O(N*N*19) > 10^4

💡 풀이 아이디어

• BFS 를 통해 로봇이 특정 몬스터가 있는 곳 까지 최단거리로 이동했을 때 전체 시간 구하기
  1. BFS 탐색으로 현재 지점부터 방문가능한 모든 지점의 최단거리 탐색
  2. 현재 지점에서 죽일 수 있는 몬스터 찾기 가장 가까운 몬스터: 거리 > 행 > 열
  3. 최적의 몬스터를 찾으면 해당 몬스터까지의 최단거리를 저장
  4. 몬스터를 다 죽이거나, 더 이상 몬스터를 죽일 수 있는 거리가 아니라면 탐색 종료

BFS로 특정 목적지까지의 최단거리를 매번 어떻게 구해야 할 때는 최단거리 저장 테이블을 만들고, 최단거리를 저장 + 탐색종료 시 초기화 하기★

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 20 → 따로 고려하지 않았음
• BFS를 진행하기에 충분

💡 풀이 아이디어

• 로봇의 현재 위치에서 BFS로 처리할 수 있는 최단 거리 몬스터 찾기
  • 같은 거리에 있는 처리 가능한 몬스터가 여럿일 경우 위 → 왼쪽 순으로 우선 순위가 존재
  • 몬스터의 위치를 우선 순위 큐를 이용하여 저장
• 최단 거리마다 우선 순위 큐에 몬스터 위치가 들어있는지 확인해야 하므로 깊이마다 확인할 수 있도록 BFS 진행
• 다음 깊이의 BFS를 진행하기 전에 몬스터가 있다면 없애고 해당 위치에서 다시 BFS 진행

이동하는 순서를 위,왼쪽 탐색하는 방식으로 하니깐 틀려서 우선 순위 큐 사용했습니다.. 앞으로 조심하기