개발 블로그

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

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #include #include #include #define max 1001 using namespace std; int n,m; int tomato[max][max]; queueq; bool visited[max][max]; int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; void bfs() { visited[max][max] = {false};..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net #include #include #include #include #include using namespace std; int n,m; int ans=0; int board[51][51]; int mov[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}}; int bfs(int a,int b) { bool v..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include #include #include #define max 1001 using namespace std; int n,m; int v; int board[max][max]; bool visited[max] = {false}; void dfs(int node) { visited[node] = true; cout

백트래킹이란 ? 현재 상태에서 가능한 모든 후보를 따라 들어가며 탐색하는 알고리즘 ex) 오목을 예시로 둘 수 있다. 오목을 둘 때 상대방의 바둑알을 어디에 두눈가에 따라 다양한 후보들이 생긴다. 즉 가능한 모든 경우를 생각해볼 수 있기에 이를 백트래킹 알고리즘이라고 할 수 있다. 알고리즘 예시1) N과 M(1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M은 전형적인 백트래킹 문제이다. 이는 1~N까지 중복 없이 M개를 선택하여 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #include #include #include #include using namespace std; int n,m; int map[8][8]; int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}}; int ret = 0; void bfs(){ bool visited[8][8] = {false}; queue q; int backup[8][8]; for(int i=0;i