Heecheol's blog

문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 간단히 말하면, 각 섬에서 바다와 만나는 칸에서 다른 섬들과의 최단거리를 찾아서 해결했다. 우선, 다른 영역을 구하는 문제들과 동일하게 모든 점을 확인하기 위해 중첩된 반복문을 이용하였다. 1인 점을 만났을때, 방문한 기록이 없다면 bfs를 이용해 섬을 찾아준다. 섬을 찾고나면 map이라는 변수는 섬 부분만 0이고 나머지는 -1로 초기화가 되어있을 것이다. 이때, 바다와 인접한 칸(0과 인접..

문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 문제를 제대로 안읽어서 오래걸렸다... 빙산이 두 개로 나눠져있는지 체크하기 위해서는 이전에 풀었던 영역 구하는 문제들을 생각하면 된다. 빙산이 두 덩어리로 분리된다는 말은 bfs를 돌렸을때 두 번 돈다는 얘기이다. 이 문제를 풀 때, 전체 빙산 배열을 이중 반복문으로 하나씩 확인해가면서 방문한 적이 없고, 0이 아닌 칸에서 bfs를 통해 확인할 것이다. bfs를 진행하면서 어차피..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 처음 풀어보는 유형이라 너무 어려웠다..기본적인 틀 자체는 BFS문제들과 비슷하지만 벽을 부순다는 조건이 추가되었다. 처음에는 queue에 들어가는 배열에 벽을 부신 수를 추가해서, 만약 부신 벽이 1이면 더 이상 1쪽으로 갈 수 없게 구현하였다. 여기까진 괜찮은데 최단거리값을 가지는 배열 result가 2차원인 것이 문제였다. BFS의 코드에서 result값이..

문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 N-Queen에서의 접근방법을 떠올리며 풀었었다. 0인 칸에 숫자가 채워지면 해당 칸을 포함하는 행과 열 그리고 해당 블럭(3x3)에서 그 숫자는 유일해야한다. 따라서 세 개의 변수를 선언하였다. 각 행과 열 그리고 블럭 안에는 1부터 9까지의 수가 한 번씩만 들어가야하므로 이차원배열을 이용했다. 예를 들어, 2번째 열에 3이라는 숫자가 들어간다면 row[1][3] = true가 되는 ..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 숫자의 순서가 고정되어있고, 연산자의 우선순위 없이 계산한다는 얘기가 중요했던 것 같다. 즉, 연산자의 순서만 바꿔주면 되고 앞에서부터 연산을 하면 된다는 얘기이다. 평소처럼 check나 visited대신 이번에는 연산자가 사용되는 것이므로 oper[i] -= 1을 해줬다. 그리고 i에 따라서 어떤 연산자인지 알 수 있으므로 if ..