BOJ
-
백준(BOJ) 16234번 인구 이동알고리즘 풀이/백준(Boj) 2019. 11. 22. 16:03
문제 : https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 풀이 : 연합이 될 수있는 칸들을 BFS를 통해서 탐색한다. 연합이 자기 자신을 제외하고 하나라도 있다면 ans를 +1 해주..
-
백준(BOJ) 14890번 경사로알고리즘 풀이/백준(Boj) 2019. 11. 16. 04:25
문제 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 : 단순히 문제에 주어진 대로 따라하는 시뮬레이션 문제였다. 행과 열을 한줄씩 담아서 경사로를 확인하는 함수에 넣어서 처리하자. 조건들을 주의하면서 푼다면 무리없이 풀 수 있었다. 자세한 것은 주석을 확인 코드 ( C++ )
-
백준(BOJ) 16948번 데스 나이트알고리즘 풀이/백준(Boj) 2019. 11. 7. 13:49
문제 : https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부 www.acmicpc.net 풀이 : 기본적인 BFS 문제였습니다. 첫 시작 구간을 fy, fx로 잡고 나아갈 수 있는 6방향을 확인합니다. 탐색을 ..
-
백준(BOJ) 16926번 배열 돌리기 1알고리즘 풀이/백준(Boj) 2019. 11. 4. 02:48
문제 : https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4 www.acmicpc.net 풀이 : 재귀적으로 배열이 끝에서만 돌도록 구현해보았다. 중요한 것은 wall을 기준으로 wall이 0,0일 때 1,..
-
백준(BOJ) 16928번 뱀과 사다리 게임알고리즘 풀이/백준(Boj) 2019. 11. 1. 01:50
문제 : https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다. 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸 www.acmicpc.net 풀이 : 최소 몇 번의 주사위를 굴렸는지 구해야 하므로 BFS로 해결하자. 큐에 시작점인 1부터 넣고 주사위의 경우..
-
백준(BOJ) 17070번 파이프 옮기기 1알고리즘 풀이/백준(Boj) 2019. 10. 31. 00:51
문제 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 풀이 : 각각 가로, 세로, 대각 규칙에 따라서 재귀적으로 호출해주자. 방향이 세로인지 가로인지 대각인지 알아야 하..
-
백준(BOJ) 3085번 사탕 게임알고리즘 풀이/백준(Boj) 2019. 10. 27. 02:05
문제 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하 www.acmicpc.net 풀이 : 상하좌우 바꿀 수 있지만 위쪽이나 왼쪽 교환은 이전 칸에 오른쪽이나 아래쪽 교환으로 구할 수 있기 때문에 아래, 오른..
-
백준(BOJ) 1937번 욕심쟁이 판다알고리즘 풀이/백준(Boj) 2019. 10. 27. 01:37
문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 풀이 : 0,0부터 n n까지 모든 경우의 수를 조사하여 최대 길이를 찾아야 한다. 이때 한 y,x에서의 길이는 이미 구해진..