1. 💎 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제도 퍼져나가는 형식으로 BFS의 전형적인 문제이다. 현재 요소를 기준으로 주위 요소들이 전염되는 방식으로 이전에 풀었던 문제가 들과 유사하다. 단지 이 문제는 전염 조건과 수행해야 하는 로직이 늘었다. 조건1. 먼저전염 조건은 인접한 칸의 인구수가 L명이상, R명 이하이다. 조건2. 전염된 나라끼리는 인구수를 다시 계산해야한다. 조건3. BFS를 한 번만 돌리는 것이 아니라 인구이동이 없을 때까지 실행해야 ..

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을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..

1. 📄 문제 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 2. 🤔 어떻게 접근할까 문제가 길어 차근 차근 그림으로 그리니 짝수와 홀수번으로 나누어졌다. 그래서 짝수와 홀수번 로직을 따로 구현한다로 생각했다. 또한 폭탄이 터지는 기준은 폭탄이 있는 위치에서 상하좌우 4개의 폭탄이 터져 없어지기 떄문에, 폭탄의 위치를 큐에 넣어 터질 시간이 되면 큐에서 꺼내어 상하좌우를 알아보기로 생각했다. 이 정도만 생각하고 바로 풀었는데 몇 몇 막히는 부분이 있었다. 3. 💡 생각해야 할 점 먼저, 폭탄은 설치 후 3초가 지나야 터진다는 ..

1. 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 2. 문제 풀이 해당 문제는 입력받은 간선의 정보대로 리스트(graph)에 담고 DFS 탐색을 진행하면 되는 문제이다. 결과는 연결 요소의 개수. 즉 노드의 집합이 몇개이냐 문제이다. 그러므로 DFS 탐색을 진행하다 해당 그래프의 탐색이 완료되면, Count를 1 더해주고 다른 노들 집합을 찾아 탐색을 진행한다. 2.1 그래프 구성 간선이 Nx(N-1)/2라면 무방향 그래프이다. 무방향 그..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 흐름 이 문제는 테스트 케이스의 제한이 없는데 N은 100,000이다. 그러므로 최대한 O(n)으로 풀어야 겠다고 생각했다. 어떻게 최대값을 찾는냐! 스티커는 총 2줄이고 인접한 스티커는 뜯으면 안된다. 만약 열의 수가 짝수이면 지그재그 방법뿐이다. 그래서 2개의 경우의 수 밖에 없지만 문제는 열의 수가 홀수일 때 이다. 예제를 분석해보면 현재 위치에서 갈 수 있는 방법은 2가지이다. 인접한 변으로 못가니, 대각선으로만 이동이 가능하다. 대..