개발 블로그

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net #include #include #include #include #include using namespace std; vector house, chicken ,pick; int n,m,t; int ret = 100000000; void dfs(int pos) { if(pick.size()==m){ int candi = 0; for(int i=0;in>>m; for(int i=..

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x >n; vectorv; for(int i=0;i>x>>y; v.push_back(mak..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #include #include #include #define max 301 using namespace std; queueq; int board[max][max]; bool visited[max][max]; int mov [8][2] = {{2,1},{1,2},{-2,1},{-1,2},{-2,-1},{-1,-2},{1,-2},{2,-1}}; // 말의 이동 int main() { int t; ci..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include #include #include #define max 51 using namespace std; int mov[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int board[max][max]; bool visited[max][max] = {0}; int n,m,x,y; int cnt=0; void dfs(int a,int b) { visited[a][b] = true; f..

재귀 함수 자기 자신을 호출하는 함수 Base Case : 간단히 결과를 반환하는 부분 Recursive Case : 자기 자신을 호출하는 부분 factorial - n==0 n! =1 // Base Case n>0 n! = n * (n-1)! // Recursive case 재귀를 활용한 flood fill 알고리즘 #include using namespace std; int n, Board[100][100]; void fill(int r,int c) { if(rn-1 || c n-1) return; //경계면을 벗어나면 return if(Board[r][c]) return; //벽이 있으면 return Board[r][c] = 1; fill(r-1,c);//위 fill(r+1,c);//아래 fill(..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include #include #include #define max 51 using namespace std; int w,h,n,m; int board[max][max]; bool visited[max][max] = {0}; int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{1,-1},{-1,1}}; //상하좌우 대각선 이동 void d..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이 문제는 dfs, bfs의 기본 문제이다. #include #include #include #include #include #define max 1001 int board[max][max]; bool visited[max] = {0}; int cnt=0; int n,m; using namespace std; //void dfs(int..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net bfs #include #include #include #include #define max 101 using namespace std; int n, com; int cnt=0; int graph[max][max]; void bfs(int node){ bool visited[max]= {false}; queuemyqueue; visited[node]=true; myqueue.push(node); whi..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #include #include #include #include #define max 101 using namespace std; queueq; int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int board[max][max]; int n,m; string s; void bfs(int x,int y){ bool visited[max][max] = {false}; visited[x][y]=true..

BFS(Breadth First Search) 그래프 순회 방법 중 하나(너비 우선 탐색) 시작 노드에서 인접노드를 방문하고, 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복한다. Queue(큐)를 이용한 BFS 풀이 입력 5(노드의 수) 6(간선의 수) 0 1 0 2 1 3 1 4 2 4 3 4 (간선이 존재하는 노드의 쌍 입력) 출력 0 1 2 3 4 #include #include #include #include using namespace std; #define max 10 int n, e; int graph[max][max]; void bfs(int node){ bool visited[max]= {false}; queuemyqueue; visited[node]=true; myqueue.pu..