오늘도 맑음

목차1. 문제 풀이2. 내가 푼 정답 (shift 연산 사용)3. 개선한 풀이 (큐 직접 구현)1. 문제 풀이2차원 평면에서 출발지점과 목적지점이 주어질 때, 장애물(0)을 이동하는 데 걸리는 최단 거리를 구하는 문제이므로, bfs로 해결할 수 있었다.다만, 시간 복잡도를 줄이는 데에서 애를 먹었다. 시간 복잡도제한 조건에서 알다시피 maps의 row, col은 최대 100이다. 따라서 row, col을 둘 다 N 이라고 하겠다.이 때, 시간 복잡도는 다음과 같다.시간 복잡도- 모든 칸을 순회 : O(N^2)- shift 연산 : O(N^2)👉 O(N^4) 최악의 경우 N 👉 O(10^8) 여기서 문제였던 부분이 1초당 10^8 연산을 할 수 있는데, 그럼 간당간당하게 되거나 안되거나 하겠다. 라는 ..

목차1. 문제 풀이  1) 테두리 구하기  2) 테두리 이동할 때, 풀이법 (❌ 주의: 칸 이동과 다름)2. 전체 코드3. 느낀 점1. 문제 풀이그림과 같이 여러 다각형이 배열 형태로 주어질 때, 테두리 정보를 배열에 저장해두어야 한다.출발지 (x, y) 에서 목적지 (x, y) 에 도달할 때까지 걸리는 가장 짧은 거리를 계산하기 위해서는 bfs 코드를 수행한다. 직사각형 입력 형식직사각형 배열은 [fromX, fromY, toX, toY] 로 주어지며, 각각 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점 정보이다.예를 들어, 가장 아래의 직사각형은 [1,1,7,4] 로 주어진다. 처음 생각한 방식처음에 생각한 방식은 직사각형이 주어질 때, 모든 선분을 1로 만드는 것이였다.그리고 1과 0(초기화) 경계에 있는 ..