궤도

문제 풀이 먼저 모든 친구 관계를 저장한다. 메모리를 아끼기 위해 myunji.tistory.com/291?category=1154147 [백준] 1707번 : 이분 그래프 문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으 myunji.tistory.com 이때 썼던 방법으로 저장했다. i번째 사람을 시작점으로 하는 dfs를 N번 돌리면서 문제의 조건에 맞는 친구 5명을 찾으면 리턴한다. 문제를 풀고 다른 사람들의 코드를 보니 친구 관계 4개를 찾는걸 종료 조건으로 한 사람들이 많았다. 근데 그거나 이거나 같은 말이니까 상관없다. 소스코드 #include #include u..

문제 풀이 myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제와 풀이가 동일하다. 오히려 이 문제는 연결된 배추의 그룹(?)수만 세면 되는거라 더 쉬운 셈이다. 소스코드 #include #include #include using namespace std; //범위 초과 때문에 상하좌우 한줄씩 추가 int matrix[52][52], M, N; pair dir[4] = {{-1, 0}, //상 {1, 0}, //하 {0, -1}..

문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 건 더이상 해당 root와 이어진 1이 없다는 뜻이니까 다시 새로운 1이 나올때까지 배열을 돌면 되겠다. 난 그냥 편하게 재귀함수 돌리려고 dfs로 했다. 그나저나 이런 문제를 풀땐 상하좌우로 이동하면서 풀어야 하는데.. 아무생각없이 상하좌우로 이동하다간 5x5배열에서 [-1][0]을 참조하거나 [6][2]를 참조하게 될 수도 있다. 이걸 해결하는 방법은 여러가지가 있지만 난 이렇게 상하좌우 테두리를 둘러주는 방법을 선호한다. 위아래 2줄씩 더 생긴다고 큰 일이 일어나진 않을테니까... 소스코드..

문제 풀이 DFS 또는 BFS로 정점 1과 연결된 정점의 수를 세면 된다. 난 그냥 편하게 DFS를 재귀함수로 구현했다. 소스코드 #include using namespace std; int matrix[101][101], cnt; bool visited[101] = {false}; //정점의 방문 여부 void dfs(int cur, int max) { //재귀함수로 구현 for (int i = 1; i > N >> M; for (int i = 0; i > first >> second; matrix[first][second] = 1; matrix[second][first] = 1; } visited[1] = true; dfs(1, N); cout

문제 풀이 그래프 탐색 방법에 속하는 DFS와 BFS를 구현하는 문제이다. DFS는 깊이 우선 탐색으로 보통 스택 또는 재귀로 구현한다. BFS는 너비 우선 탐색으로 보통 큐로 구현한다. BFS와 DFS의 그래프 순회 순서를 나타낸 그림이다. 대충 BFS는 왼쪽->오른쪽, DFS는 위->아래로 생각하면 된다. 소스코드 #include #include #include #include using namespace std; int matrix[1001][1001]; //정점 i와 j 사이에 간선이 존재하면 matrix[i][j]=1 bool visited[1001] = {false}; //정점의 방문 여부 void dfs(int start, int max) { //스택으로 구현, 재귀로 구현해도 됨 stack..