Heecheol's blog

문제 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 ..

문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 dfs를 이용해 n / 2만큼의 팀원이 차면 계산을 해주도록 하였다. 순서는 상관없으므로 idx라는 파라미터를 이용해 선택된 팀원부터 진행할 수 있도록 하였다. check[i]를 true로 바꿔주면 count가 n / 2가 된 시점에는 true인 사람 반, false인 사람 반이 돼서 팀이 만들어진다. 이후에 반복문을 이용해 true라면 더해주고, false라면 빼주도록 한 뒤에 절댓값을 이용해 기존의 re..