컴굥일지

문제 https://www.acmicpc.net/problem/11724 문제 내용 정점과 간선의 정보를 입력받아, 몇 개의 연결 요소로 이루어져 있는지 구하면 된다. (사이클을 말하는 게 아니라 연결 요소를 말하는 것) 문제 풀이 모든 노드에 대해 아직 방문하지 않은 경우, bfs를 돌리면 된다. 나는 이 문제를 인접 행렬로 구현하지 않고, 인접 리스트로 그래프를 구현했다. 코드 #include #include #include using namespace std; int n, m; vector arr[1001]; int visited[1001]; int main() { cin >> n >> m; int node1, node2; for (int i = 0; i > node1..

문제 https://www.acmicpc.net/problem/1388 문제 내용 - 와 | 로 이루어진 바닥 장식 모양이 주어진다. 만약 가로로 - 가 이어져있거나, 세로로 | 가 이어져있으면 각각은 하나의 나무 판자이다. 바닥의 배열이 주어지고, 나무 판자의 개수를 구하면 된다. 문제 풀이 dfs로 간단하게 풀이할 수 있다. 현재 칸이 - 이면 무조건 오른쪽 칸이 - 인지 확인하고, 현재 칸이 | 이면 무조건 아래 칸이 | 인지 확인하면 된다. 코드 #include using namespace std; int n, m; char arr[50][50]; int visit[50][50]; void dfs(int cnt, int r, int c) { visit[r][c] = cnt; if (arr[r][c..

문제 https://www.acmicpc.net/problem/1260 문제 내용 그래프에 대한 내용을 입력받고, V번 정점부터 DFS와 BFS를 수행한 결과를 출력하면 된다. 문제 풀이 인접리스트 방식으로 문제를 해결해 보았다. 인접 행렬로도 풀릴 것 같기는 한데, 노드가 1000개까지 될 수 있어 인접 행렬을 arr[1001][1001] 이런 식으로 선언을 하게 되면 메모리 초과가 발생할 수도 있을 것 같다. (ide에 제한이 있을 수도 있어서...) +) 백준에서 다른 사람 제출 내역을 보니, 인접행렬로 해도 문제를 풀 수 있다. 하지만 언젠가 N이 너무 커질 때를 대비해서 인접 리스트 방식도 알아두면 좋을 것이다. 코드 #include #include #include #include using n..

문제 https://www.acmicpc.net/problem/2667 문제 내용 0은 집이 없는 곳, 1은 집이 있는 곳이다. 집들이 서로 이어져있으면 같은 단지에 속해있다. 단지의 개수를 출력하고, 각 단지에 포함된 집의 개수를 오름차순으로 정렬하여 출력하면 된다. 문제 풀이 bfs/dfs를 통해 문제를 풀 수 있다. (dfs로 풀었다.) 일단 dfs를 돌며, 서로 이어진 집끼리 단지 번호를 같게 하여 used배열에 추가한다. 모든 집에 대해 dfs 탐색이 끝나면, used배열에 있는 값을 카운트하여 출력하면 된다. 코드 #include #include #include using namespace std; int dr[4] = {1, -1, 0, 0}; int dc[4] = {0, 0, 1, -1};..

문제 링크&사진 문제 내용 1이 배추가 심어진 곳, 0이 그렇지 않은 곳이다. 지렁이가 있으면 배추를 해충으로부터 보호할 수 있는데, 인접한 배추들끼리는 지렁이 하나로도 충분하다. 배추가 심어져 있는 위치를 입력받아, 지렁이가 최소 몇 마리나 필요한지를 출력하면 된다. 문제 풀이 이 문제는 bfs, dfs 둘 모두로 풀 수 있는 문제이다. 코드 BFS 풀이 #include #include #include using namespace std; int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, 1, -1}; int m, n, k; void bfs(vector &arr, vector &visited, int r, int c) { queue q; q.push({r, c}); vi..

문제 https://www.acmicpc.net/problem/2210 문제 내용 숫자판의 임의의 위치에서 시작하여, 5번 이동하면서 만들 수 있는 수의 개수를 출력하는 문제이다. 문제를 해결하기 위해 dfs를 사용했으며, 중복을 확인하기 위해 set을 사용했다. 문제 풀이 그렇게 어려운 문제는 아니다. 나는 dfs함수를 만들어서 재귀로 이 문제를 해결했다. 일단 5번을 이동하면 재귀를 끝낼 수 있도록 dfs()에 조건문을 넣어주었다. 다만, return을 하기 전에, set에 값을 집어넣어서 중복을 제거해주었다. 나중에 출력시 set.size() 해주면 된다. dfs()에서 탈출 조건을 넘어간다면, 상하좌우로 이동을 하도록 코드를 짰다. 이때 x,y좌표가 범위를 벗어나는 것을 방지하기 위해 체크를 해주..