차곡차곡 성 쌓기

1. 문제[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.시추관은 위 그림처럼 설치한 위치 ..

1. 문제  2. 접근문제 읽고 평소에 풀던 BFS 문제들이랑 비슷해서 별로 생각 안하고 풀다가 시간초과가 났다. 접근1. 모든 좌표를 다 돌면서 모래성(1~9)인 경우 주변(대각선, 상하좌우)을 체크한 후 무너지면 체크해주기, 그리고 체크 된 모래성들을 한 번에 0으로 표시하기 이렇게 풀었더니 시간초과가 났다. 로직에는 문제가 없는 줄 알고 모든 좌표가 아닌 -> 모래성 좌표만 큐에 저장해서 찾아가는 식으로 바꿔봤다. 하지만 이 방법도 시간초과가 났다. 시간 복잡도를 구해보니 모래성의 크기가 1000X 1000 = 10^6(백만)이고, 모래성의 개수가 평균 50%라고 했을 때 50만이고 BFS니깐 한 파도가 칠 때 평균 50만 * (8방향)이고 파도가 약 (Max(H, W) 이니깐 약 400,000만...

거울의 반사되는 조건과 기존에 자주 풀던 최단 경로가 아닌 도달할 수 있을 때 '거울의 최소 수'를 구하는 문제라서 더욱 어렵게 느껴졌다.문제를 읽고 구현을 BFS로 할지, DFS로 할지 고민했는데 BFS로 하게될 경우 거울의 개수를 어떻게 관리하고, 그에 따른 visited 배열을 관리하는 것이 어려울 것 같아서 바로 DFS로 노선을 틀었다. 최소 거울의 개수를 구하면 되니깐 거울을 1개 이용했을 때 반대편 문제 도달하는지 확인하고, 도달 못하는 경우 거울의 수를 늘려서 다시 2개, 3개,, N개가 될 때까지 DFS를 반복했다. 그러니 당연하게도 시간초과가 났다.  이 문제는 BFS로 풀어야되는 문제였다. 다른 사람의 BFS 풀이를 보면서 내가 잘못 접근한 부분을 찾아봤다. 1. 거울의 개수를 어떻게 ..

✓ 문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 그래프들의 단방향 정보가 주어지고 출발 도시로부터 최단 거리가 X인 다른 정점들을 찾는 문제이다. 단순히 거리가 X인 것이 아니라 최단거리여야 한다. ✓ 풀이 처음에는 DFS탐색을 이용하여 dpeth가 X일 때를 찾았다. 하지만 문제는 최단거리를 구해야 된다는 점이었다. 최단거리를 갱신해주기 위해서는 결국 모든 탐색을 다 해줬어야 했다. 비효율적인 것 같아서 더 효율적인 방법을 찾았..

1. 📄 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - 반드시 3개의 벽을 세워서 확보할 수 있는 안전 구역의 최댓값을 구하기 2. 🤔 어떻게 풀까? 문제를 처음 봤을 때 대체 어떠한 방법으로 벽을 세울 위치를 정해야될지 난감했다. 바이러스를 중심으로 한다해도 어렵고, 벽을 중심으로 해도 어렵고.. 모르겠다가 넉넉한 시간과 작은 N과 M의 개수를 보고 완전 탐색을 생각했다. 그후 과연 시간 조건을 충족할 수 있을지 계산을 해보았고 아주 넉넉했다. 그래서 벽을 세울 수 있는 모든 경우의 수로 벽을 세우고, BFS ..

1. 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net i번째 숫자가 j번째에 도달할 수 있는지 출력한다. 가능하면 1, 불가능하면 0을 출력 2. 어떻게 풀까? 입력으로 주어지는 형식이 인접행렬일 뿐 결국 간선의 정보이다. 그러므로 평소 풀던것 처럼 `ArrayList []`를 생성하여 간선의 정보를 저장한 뒤, 1부터 N번째 숫자를 차례로 BFS 탐색을 진행하기로 했다. 만약 1을 시작으로 BFS 함수를 호출하면 1에서 다른 요소인 {2,3,4,5,6} 에 도달할 수 있는 탐색을 통해 알아낸다. // 1부터 N까지 각 BFS 탐색 ..

1. 💎 문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 케빈 베이컨은 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다. 2. 🤔 어떻게 풀까? 사람마다 한명 씩 모든 사람과의 케빈 값을 구한 후 모두 더해, 가장 낮은 사람을 출력하면 되겠다. 케빈 값을 구하는 방법은 DFS를 사용해서 깊이를 더해주면서 구하면 되겠다. 하지만 틀렸다. DFS를 사용하면 모든 사람과의 관계의 단계를 알 수 있지만..

1. 💎 문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다. 3. 💡로직 1. 지도를 입력 및 시작점 받기 이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..