개발 블로그

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 기존 BFS 방식(상,하,좌,우)에서 이동할 수 있는 경로가 8개가 추가되었습니다. (나이트의 이동경로 8개) 문제에서 주어지는 조건은 나이트처럼 이동할 수 있는 횟수 K와 w(가로)*h(세로)와 2차원 배열입니다. 그래서 기존 2차원 배열이 아닌, 나이트처럼 이동한 횟수를 담아야 하기에, 3차원 배열로 선언해 주었습니다. d[a][b][c] = 원숭이가 a,b로 이동하기 위해 k..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 이 문제는 간단하지 않은 BFS 문제입니다. 빈 물통 A, B의 용량과, 가득 찬 물통 C의 용량이 주어집니다. 이제 여기에서 각각의 물통에 물을 부어서 한 쪽이라도 물통이 비면 모든 가능한 C의 물의 양을 출력하는 경우입니다. 로직 from -> to (모든 from의 물의 양을 부어준다.) from의 물의 양 0으로 초기화 to에 가득찬 물의 양이 c의 양을 초과한 경우(f..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 DFS + 백트래킹 문제입니다. 보자마자, DFS보다 백트래킹 먼저 생각했습니다. 왜냐하면, 모든 말이 지날 수 있는 최대 칸수를 구해야 하기 때문입니다. 그래서 DFS로 탐색하면서, 조사한 모든 경우의 수(말이 지날수 있는 모든 경우의 수)들 중 최댓값을 구해주면 됩니다. #include #include using namespace std; char board[21][21]; ..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 백준 골드5 난이도이고, 비교적 간단한 DFS 였습니다. 적록색약인 사람(빨강, 초록 구분 x)이랑, 적록색약이 아닌 사람(빨강, 초록 구분 o)의 DFS 함수를 각각 따로 만들어주었습니다. 적록색약인 사람의 경우에는 기준점이 빨강이면, DFS함수를 돌렸을 때 상하좌우의 배열값이 빨강이랑 초록이면 DFS함수를 재귀적으로 돌려주는 방향으로 알고리즘을 설계하였습니다. 그렇지 않은 경우(파랑)일..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 이 문제는 막연하게, DFS로 풀면 안됩니다. 높이, 너비가 500이기에 너비 우선 탐색으로만 풀려면 정말 오랜 시간이 걸리기 때문입니다. 그래서 (DP + DFS)로 풀 수 있습니다. #include #include using namespace std; int board[501][501]; int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; int dp[501][501];..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net #include #include #include using namespace std; int h; int board[101][101]; bool visited[101][101]; int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; int maxh = 0; void dfs(int x,int y,int num) { visited[x][y] = true; for(int i=0;in..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net #include using namespace std; int board[501][501]; bool visited[501]; int cnt=0; int n,m; // n => 정점의 최대 수 m=> 간선의 수 void bfs(int node) { for(int i=2;in>>m; for(int i=0;i>a>>b; board[a][b] = board[b][a] = 1; } bfs(1..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net #include #include #include using namespace std; int n,m; int board[501][501]; bool visit[501][501] = {false}; vectorv; int wid; int mov[4][2] ={{-1,0},{1,0},{0,1},{0,-1}}; void dfs(int x,int y) { wid++; visit[x][y] = true; for..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net #include #include #define max 101 using namespace std; int a,b; int board[max][max]; int x,y,n,m; int visited[max] = {0}; int cnt[max] = {0}; void bfs(int node) { queueq; q.push(node); while(!q.empty()){ node = q..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #include #include using namespace std; bool visited[200001] = {false}; int main() { int start,end; queueq; cin>>start>>end; q.push({start,0}); visited[start] = false; while(!q.empty()) { int position = q.fron..