내가 생각 했던 전반적인 개요도
[ ] Java에서 Input에 대해 금방 읽어낼줄 알아야 한다. (기본)
기본 (bufferedReader를 이용하거나 Scanner를 이용하거나 둘 다 할 줄 알아야 한다)
[ ] bfs를 생각없이 바로 구현해낼수 있어야 한다. (개념및 숙련도) (택시 투 승객)
→ bfs에서 조건들이 무엇인지 확인해야한다.
승객이 없는 모든 빈 공간들은 0으로 되어 있다.
승객을 map위에 표기할 것인지 말것인지는 내 자유 ← bfs를 쓸때는 map에 표기해주는게 편하다
어차피 bfs에서 찾으면 → 최단거리가 된다.
그러므로 현 택시위치로부터 bfs로 쭉 뻗어나가면서 승객 위치
map에 표기했다면 map위에서 mpa[nx][ny] ≠0; map[nx][ny] ≠1인 경우에 최단거리에 들어가 있는 승객들을waitList에 넣어주도록한다.
[ ] List정렬에 대해서 다방면으로 익숙해져야 한다. (객체 정렬 테크닉)
이중 어떤 승객을 태울것인가에 대해서는 → arrayList안에서 행번호 순 그래도 같으면 열번호 순으로 정렬을 해준다 → 그중 맨 앞에 있는 승객을 골라준다.
맨 앞의 승객의 목적지를 확인한다 → 그 목적지로 간다
[ ] 여기서는 위의 조건과 다른 bfs가 쓰인다. (승객 투 목적지)
→ 위의 택시가 최단거리 승객에게 가는거랑은 조건이 달라진다. 그렇기에 같은 bfs를 재사용하기 위해서는 조건에 따라 분기처리해줘야 한다. 하지만 조건에 맞춰 코드 리팩토링하기 좀 힘들어진다면 그냥 줄수가 많더라도 bfs두개 사용하는게 좋을 것 같다.
[ ] 알고리즘 풀이 설계 이슈
→ 위의 문제를 풀때 이슈중 하나 map상에 승객및 목적지를 숫자로 표기할 것인가?
사실상 승객의 좌표와 목적지 좌표가 모두 내가 가지고 있기때문에 승객 list를 가지고 있고 이 승객 List를 조회하면서 bfs에서 돌때마다 그 승객의 위치인지 또는 그 승객의 목적지인지를 확인할수 있다.
이때 list로 승객을 관리하게 되면 → while문 한 번당 for loop를 돌면서 승객을 모두 조회해야 한다. 그렇게 안할려면 hashmap으로 승객을 관리해주고 끝나면 제거해주는 형식을 취하는게 더 낫다
(hashmap 숙련도 중요)
승객, 목적지 모두 map상에 표기해주고 분기처리를 잘해준다.
→ 이거 절대 안됨 승객 위에 목적지로 덮힐수 있다.
승객만 map에 표기하고 목적지는 좌표로 조회한다
승객, 목적지 모두 좌표로 관리한다.
→ 여기서 빠르게 결정하고 구현할수 있어야 한다.
그리고 승객을 태웠는지 태우지 않았는지 분기처리를 해줘야 한다 bfs를 한번에 처리할려면
[ ] 예외케이스 조건
→ 예외케이스가 무엇이 있을지 생각해본다. (예외 조건들을 머리로 생각해보고 문제마다 있었던 부분들을 모두 기록해두자)
BFS풀면서 막혔던 점
→ 기존에는 칸의 숫자를 세는 등의 문제가 많이 나왔었다 하지만, 스타트택시의 경우 길을 따라서 가고 그 이동거리를 요구했다. 이부분에 있어서 달랐었다.
for(int i=0; i<4; i++) {
newTaxiX = taxiX + dx[i];
newTaxiY = taxiY + dy[i];
if(newTaxiX>=1 && newTaxiX<N+1 && newTaxiY>=1 && newTaxiY<N+1 && visit[newTaxiX][newTaxiY] == false) {
if(map[newTaxiX][newTaxiY] !=1) {
visit[newTaxiX][newTaxiY] = true;
Taxi newTaxi = new Taxi(newTaxiX, newTaxiY);
q.add(newTaxi);
movement+=1;
}
}
}
}