devlog

출처 : 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 방법 익은 토마토의 인접한 토마토들이 익어가는 것으로 보아 그래프 문제이다. 인접한 단계에 따라 기간이 흘러가므로 bfs문제로 볼 수 있다. 그런데 이 문제는 bfs의 시작점 즉 처음부터 익어있는 토마토가 한 개가 아니므로 시작점을 여러개 해주어야한다. 그러기 위해 입력을 받을 때 처음으로 익어 있는 토마토의 위치를 저장해 둔다. 그리고 bfs를 돌기위해 저장해둔 토마토 위치를 모두 큐에..

출처 : 1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 방법 삼각형을 위에서부터 내려오면서 자신의 인덱스가 자신이 속한 층내에서 i 번째라면 바로 위층의 i-1,i 번째 인덱스 중 큰 수를 더해주면서 가장 바닥까지 내려와 바닥중 가장 큰 수를 출력하면 된다 #include using namespace std; vector triangle; int N, ans; int main() { cin >> N; triangle.resize(N); for (int i = 0;i < N;i++) { for (int k = 0;k < i+1..

출처 : 12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 방법 visited배열에 현재 위치를 방문했는지를 기록하고 하지 않았으면 bfs로 방문하면 된다 bfs를 이용하면 자동적으로 시간이 빠른 것부터 참 색 하여 답에 도착하므로 bfs를 사용하였다 x가 현재위치다. x-1 >=0 이고 x-1 지점을 방문하지 않았더라면 x-1 지점을 방문한다 여기서 현재 위치가 목표 위치보다 작더라도 x-1을 해주어야 한다 왜냐하면 ..

출처 : 18428번: 감시 피하기 (acmicpc.net) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 방법 완전 탐색 + DFS로 풀이할 수 있다. 벽을 세우는 경우를 완전 탐색으로 푸는데 시간을 줄이기 위해 빈 공간을 미리 리스트에 저장해둔다 벽이 3개 생성되면 check 함수를 호출하여 각 선생님의 동서남북 방향을 검사한다 while 문을 통해 board안에서의 동서남북중 한쪽씩 방향을 정해서 검사한다. 만약 검사 중 벽이 나타나면 다른 방향으로 넘어가고 검사중 학생이 나타나면 retu..

출처 : 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 방법 DFS로 완전 탐색으로 풀어야 한다. 연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고 dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다. max_num = -987654321 min_num = 987654321 def dfs(index, sum): glo..

출처 : 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 방법 DFS함수의 인자로 index를 받고 재귀 호출하는 방식으로 문제를 풀이하였다. 만약 index가 삭제할 노드의 인덱스인 경우 삭제할 노드의 부모 노드의 자식이 1명일 경우(삭제당하는 노드 하나) cnt를 +1 해주었다. 그리고 return을 함으로써 삭제할 노드의 자식은 탐색하지 않았다 index가 삭제할 노드의 인덱스가 아닌데 자식이 empty인 경우에도 cnt를 +1 해주었다. 다음 자식이..

출처 : 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 방법 입력받을 때부터 S와 D 지점의 좌표를 기록하고 water의 좌표 벡터에 기록하였다 BFS를 시작할 때 queue에 water의 좌표를 먼저 추가 해준 후 고슴도치의 위치를 que에 넣어 주었는데 이유는 water을 먼저 BFS 하고 그 길을 고슴도치가 갈 수 있냐 없냐 판단을 하기 위해서 이다 (고슴도치를 먼저 이동시키면 동시에 물이 들어오는 경우 복잡해짐) 그런 후 BFS를 돌며 다음 좌표의 board(땅) ..

출처 : 2206번: 벽 부수고 이동하기 (acmicpc.net) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 방법 처음에는 저번에 풀었던 백준 14502번 연구소가 생각나서 완전탐색 + BFS로 풀려고 했으나 이렇게 풀면 시간 초과가 난다 그래서 벽을 부수는데 greedy한 방법이 있을까 생각 해 봤지만 떠오르지 않아 다른 분들의 풀이를 보니 큐에 추가할때 3차원으로 x, y좌표와 추가적으로 이까지 오면서 벽을 부수었는지 기록해 주었다. 결국 큐에 추가해주어야 하는 경우는 ..

출처 : 10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 방법 적록색약이 아닌 경우는 일반적인 BFS 풀이하면 된다 하지만 적록색약인 경우는 R, G인 경우를 판단하여 불린 값에 넣어 두고 따로 이런 경우를 빼내어서 R,G을 같은 색으로 취급해주었다. BFS1이 적록색약이 아닌경우 함수 BFS2가 적록색약인 경우의 함수이다. visited를 중간에 0으로 초기화해주어야 BFS1과 BFS2 가 섞이지 않는다 #include #define pii pair..

출처 : 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 방법 BFS를 이용한 완전 탐색 문제이다 이중 for루프를 돌며 방문하지 않았으며 집인 곳이 보이면 BFS를 그 지점 부터 시작하여 연결된 덩어리의 개수를 세어주면 된다. 실수 for (int i = 0;i < N;i++) { for (int j = 0;j < N;j++) { if (board[i][j] == '1') { if (visited[i][j] == 0) { house_num.push_ba..