30분이면 풀 수 있을 줄 알았지만 몇 시간을 고민한 문제이다. 각 열을 돌면서 매번 bfs를 탐색해도 시간초과에 안 걸릴 것 같았는데, 효율성 테스트에서 전부 시간 초과가 나서 bfs 탐색이 끝나면 각 열에 오일 개수를 추가하는 로직으로 풀이에 성공했다. 로직 일반적인 bfs와 다른점은 bfs 탐색이 끝나면 석유가 있는 열 set을 따로 만들어서 set을 순회하며 원래 oil 리스트에 인접 영역의 석유의 양인 cnt을 더해주는 것이다. 이렇게 하면 bfs 탐색은 한 번만 실행하고 석유가 있는 인접영역을 모두 열에 추가하여 답을 구할 수 있다. 최종 코드 from collections import deque def solution(land): answer = 0 n, m = len(land), len(l..
지난겨울 카카오 인턴을 지원하면서 이미 풀어보았던 문제였다. 그때는 인접 리스트를 구성해서 실제로 BFS 탐색을 돌리다가 시간 초과로 실패했었다. 이번에는 방법을 달리해서 풀이에 성공했다. 로직 각 노드의 들어오는 간선과 나가는 간선을 구하면 생각보다 쉽게 풀리는 문제다. 각 그래프마다 특정 규칙을 만족시키는 노드가 1개씩 존재한다. 정점은 들어오는 간선이 없으므로 들어오는 간선의 개수가 0이고, 나가는 간선의 개수는 문제의 조건에 따라서 2개 이상이다. 막대 모양 그래프는 이어진 노드중에 1개가 나가는 간선이 없는것이고, 8자 모양 그래프는 나가는 간선이 2개이면서 들어오는 간선은 2개 이상이다. 도넛 모양 그래프는 정점에서 나가는 간선의 개수 - 막대 모양 도형의 개수 - 8자 모양 도형의 개수를 하..
오랜만에 풀어보는 알고리즘 문제였다. 왠지 문제가 그리디하게 접근하면 풀릴것 같아서 시도했더니 한시간만에 풀 수 있었다. 로직 첫번째로 targets 배열을 정렬해야 한다. 어떤 기준으로 정렬하냐가 중요한데, 나는 s를 오름차순으로 정렬했다가 최솟값에 맞지 않는다는 것을 깨닫고 e을 오름차순으로 정렬했다. for문을 돌며 미사일이 날아오면 미사일의 시작지점인 s와 e중 한 지점에서 요격해야 한다. 미사일 하나에 맞춰서 요격을 하고 다음 미사일이 현재 요격 기준에 맞지 않으면 answer를 추가하고 요격 기준을 갱신하는 방식으로 생각하면 된다. 최종 코드 import java.util.*; class Solution { public int solution(int[][] targets) { int answe..
BFS + 조건이 붙은 문제였다. 문제를 읽고 예전에 했던 게임이 생각나서 재미있게 풀었다. 로직 먼저 board를 순회하며 아직 계산되지 않은 노드를 INF로 초기화 하고, 시작 지점과 도착 지점의 좌표를 저장한다. 시작지점에서 BFS 탐색을 시작하는데, 다른 점은 우선순위 큐를 사용한다는 것이다. 우선순위 큐를 이용하면 상하좌우 중 지금까지 가장 적은 방문 횟수를 가진 노드를 먼저 방문하게 되기 때문이다. 상하좌우를 선택하였다면, D를 만나거나 배열에 끝에 다다를때까지 계속 같은 방향으로 진행한다. 그리고 도착한 노드에 횟수를 더해주고 계속 탐색하면 된다. 최종 코드 import java.util.*; class Solution { static int[] dRow = {1, -1, 0, 0}; sta..
