문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 방법 벽을 부쉈을 때 이동할 수 있는 칸의 갯수를 구하면 되는 문제다. 단, 모든 벽마다 탐색을 해서 이동할 수 있는 칸 개수를 구하면 시간 초과가 발생한다. 예를 들어 다음과 같은 케이스가 들어온다고 해보자. 예시: 6 6 101010 000000 101010 000000 101010 000000 1에서 탐색을 시작할때마다 모든 0의 개수를 반복적으로 구하기 때문..
그래프 탐색
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 방법 그래프 탐색을 활용한 구현 문제다. 주의해야 할 것은 시작부터 덩어리가 이미 분리되어 있는 케이스가 있기 때문에 녹이기 전에 먼저 덩어리 개수를 확인해줘야 한다. 따라서 현재 빙산의 높이 정보를 토대로 빙산의 덩어리가 두 덩어리 이상이면 현재 시간을 출력하고, 그렇지 않다면 문제의 설명대로 빙산을 녹이고 시간을 증가시키면 된다. 빙산의 덩어리 개수를 세는 알고리즘은 BFS나 ..
문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 방법 2206번 벽 부수고 이동하기와 비슷한 문제다. 이 문제에서는 벽을 K개만큼 부술 수 있는게 차이점이다. 비슷하게 풀되 벽을 1개까지 부쉈던 부분을 K개까지 부술 수 있게 처리하면 된다. 코드 #include #include #include #include #include #include using namespace std; int dy[] = ..
문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 문제에 설명되어있는 것처럼 i번 위치와 j번 위치를 바꾸는 연산을 K번 했을 때 나오는 수들의 최댓값을 구하면 된다. 헷갈릴 수 있는데, 탐색 과정 중의 최댓값을 구하는 게 아니라 탐색을 K번한 후의 최댓값을 구하는 것이다. 예를 들면 예제 입력2의 132 3에서 연산을 2번 했을 때의 수는 132, 213, 321이고 이 중 최댓값은 321이지만 연산을 3번 했을 때는 123, 231, 312로 최댓값은 312가 나온다. 그리고 132->123 , ..
