1. 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. Error Point 이중 반복문을 빠져 나오는 경우에서 생각하기 오래 걸렸다. flag 변수를 하나 두어서 이중 반복문을 빠져 나오는 것이 아닌 실제 값을 더하는 부분에서 처리하자 3. 풀이 Point 도시의 좌표, 인구 수를 멤버 변수로 가지는 static class를 만든다. 주요 변수 및 자료구조 visited 배열 : BFS 탐색을 위한 방문 배열 cityL..
1. 문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 2. 풀이 Point 파이프의 상태에 따라 움직일 수 있는 경우가 다르기 때문에 이를 분기점으로 나눠주는 것이 중요 파이프의 상태에 따라 switch case로 나누어 주었고 파이프의 상태에 따라 갈 수 있는 경우를 재귀 함수를 통해 탐색 반복적으로 나오는 경우가 많으므로 이동하는 건 함수로 처리 뒤로 돌아오거나 갔던 곳을 다시 가는 경우는 없기에 visited..
1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이 Point (1) 벽을 만날 때마다 벽을 부수고 bfs 돌리는건 시간 초과가 난다. 벽을 탐색한다면 NM의 시간이 걸리고 이에 대하여 각각 bfs로 탐색하므로 (NM)^2의 시간이 걸린다. (2) 벽을 부쉈는지 안 부쉈는지 객체 안에 flag 변수를 두거나 visited 배열을 boolean으로 두는 경우는 탐색을 할 수가 없거나 잘못된 값을 반환한다..
1. 문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2. 풀이 Point 입력을 받을 때 처음 익은 토마토의 좌표를 미리 queue에 넣어두고 그곳을 방문처리한다. 처음 입력을 받았을 때 모두 익어있을 경우가 있으므로, 이를 탐색한다 그 후 BFS 탐색을 진행하면서 토마토가 익는 경우와 익는 day를 갱신한다. 탐색을 마쳤을 때 안 익은 토마토가 있는 경우 -1 3. 소스 코드 package bfs; import ..
1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 Point 익은 토마토가 처음에 여러개가 있을 경우 동시에 진행됨을 간과함 입력을 받을 때 처음 익은 토마토의 좌표를 미리 queue에 넣어두고 그곳을 방문처리한다. 처음 입력을 받았을 때 모두 익어있을 경우가 있으므로, 이를 탐색한다 그 후 BFS 탐색을 진행하면서 토마토가 익는 경우와 익는 day를 갱신한다. 탐색을 마쳤을 때 안 익은 토마토가 있는 경우 ..
1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 Point 우선순위에 대하여 정렬하는 방법을 찾지 못함(먹이 큐를 따로 둔다는 것을 생각 못함)…. BFS를 한 번만 돌고 판단하려함 → 먹이를 먹고 난 후 우선 순위가 달라진다는 것을 생각 못함 먹이를 먹고 다시 탐색하려 할 때, 처음 상어가 있었던 위치도 다시 탐색해줘야 하는데, 이를 bfs에서 조건을 걸어주려함 → 상어가 있는 위치는 9인데, 이를 0으로 바꿔주지..
1. 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 2. 풀이 Point 링크와스타트 (백준 15661)과 굉장히 유사한 문제이다. 주요 입력 자료구조 peopleCityMap : 도시 별로 인구수가 저장된 Map List[] linkList : 도시 별로 연결되어 있는지를 저장한 연결리스트 boolean[] visited : 도시를 2개의 구역으로 나누기 위한 배열 N개의 구역이 있을 때, A, B 구역으로 나누는 부분 visited 배열의 BackTrac..
1. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 풀이 백준 골드4에 해당하는 DFS 문제이다. 우선 입력으로 주어지는 배열의 row와 column을 통해 정수형 2차원 배열을 구성하고 다음 줄부터 주어지는 배열의 값을 2차원 배열에 값을 저장한다. 그 후 while 무한 반복을 돌면서 다음과 같은 로직을 순서대로 수행한다. 1. 1년 추가 2. 얼음 구역의 개수 체크 ( 이는 처음으로 주어지는 배열의 값이 이미 다 녹아있거..
