IT 개발일지

문제 접근BFS를 활용해서 모든 sources에 대한 최단 거리를 구할 수 있다.각각의 거리가 1이기 때문에 다익스트라를 사용하지 않고 풀 수 있다.BFS를 사용할 때, destination에서부터 시작하는 게 직관적이고 풀이도 깔끔하다.만약 매 sources의 원소마다 반복한다면, 방문처리 등을 제대로 처리하지 않으면 매번 그래프를 탐색해 시간초과 이슈 가능n이 최대 100,000이어서 인접 행렬 대신 인접 리스트 활용 (메모리 초과 이슈 가능)적용 알고리즘BFS시간복잡도지역의 수 : 3 왕복 정보 가능 r = 2 시간복잡도 : O(n + r)만약 모든 sources에서 각각 BFS를 돌린다면 500(sources최대 개수) x 600,000 = 약 3억번의 연산 이슈시행착오BFS를 탐색할 때, 거리를..

문제 접근 - N * N 공간에 물고기와 아기 상어 1마리 존재 => 행과 열이 N으로 같은 grid - 아기 상어의 정보 - 초기 크기 : 2 - 칸 통과 조건 : 자신의 크기보다 작거나 같은 물고기는 지나갈 수 있음 - 잡아먹는 조건 : 자신의 크기보다 작은 물고기만 먹을 수 있음 - 이동 시간 : 1초(즉, 격자 1칸씩 옮기는 데 1초씩 걸린다고 생각) - 이동 방향 : 상, 하, 좌, 우 => dy, dx technique 사용 - 이동을 완료했으면, 동시에 물고기를 먹음(물고기를 먹는 시간은 걸리지 않음) - 성장 조건 : 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기 1 증가! - 아기 상어 위치 이동 조건 - 먹을 수 있는 물고기가 1마리라면 => 그 물고기 먹음 - 하지만 복수개라면 ..