[백준] 7576번: 토마토 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 【 풀이 】 이 문제는 시작점이 여러 개로 주어질 수 있기 때문에, 여러 정점에서 동시에 출발할 수 있도록 해주어야 한다. 즉 모든 시작점(1) 들을 큐에 밀어 넣어서, bfs를 정점들마다 번갈아가면서 탐색할 수 있게끔 해주면 된다. 그리고 날짜를 기록하는 게 곧 탐색의 거리를 의미하기도 하기에 배열마다 거리..
[백준] 1074번: Z [C++]
알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 【 풀이 】 중학교 때 배운 좌표와 그래프에서 '사분면'이란 개념을 생각하면, 배열을 이용하지 않고도 쉽게 해결 가능하다. 일단 이 문제는 배열에 접근하는 식으로는 해결하기 힘들다. 이 문제에서의 최댓값인 2의 15 제곱은 32768이고, 32768의 제곱은 1억이 넘어가기 때문이다. 따라서 이 문제는 분할, 정복으로 배열을 계속 쪼개가면서,..
[백준] 2630번: 색종이 만들기 [C++]
알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 【 풀이 】 1780번과 거의 유사한 분할, 정복 문제이다. https://baehoon.tistory.com/62 [백준] 1780번: 종이의 개수 [C++] 알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는..
[백준] 1697번: 숨바꼭질 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 【 풀이 】 1차원 배열에서의 BFS 로 해결할 수 있는 문제이다. 수빈이의 현재 점(N) 부터 BFS 를 해서 +1, -1, *2를 했을 때 나오는 위치들을 모두 방문처리 해주고 그 위치에 도달했을 때의 시간을 따로 기록해주면 된다. 【 코드 】 #include #include using name..
[백준] 1932번: 정수 삼각형 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 【 풀이 】 삼각형의 규칙을 구하면 된다. 2차원 배열 dp에 입력 받고, 각 칸까지 선택된 수의 합을 각 칸에 다시 저장한 2차원 배열을 dp라고 하자. dp[1][1] = dp[1][1] dp[2][1] = dp[1][1] + dp[2][1], dp[2][2] = dp[1][1] + dp[2][2] 이다. 3번째 층부터, 가운데의 수들은 양쪽 대각선에 저장된 숫자 중 가장 큰 값과 더해져야 한다. 즉, dp[3][1]..
[백준] 14940번: 쉬운 최단거리 [C++]
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크: https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 【 풀이 】 모든 정점들을 방문하면서, 각 정점마다 목표 지점까지의 거리를 다른 배열에 기록해 주면 되는 문제이다. BFS를 이용하여 쉽게 해결할 수 있다. 단, 목표 지점을 기준으로 BFS 를 시작해야 원하는 답을 얻을 수 있다. 왜냐하면 목표 지점에서부터 거리가 0으로 시작하기..
