MZ 개발자

이 문제는 정점 쌍이 주어지면 트리의 부모가 누구인지 찾는 문제이다. 문제의 예제 입력이 너무 깔끔하게 되어있어서 쉽게 생각할 수 있지만 현재 노드에서 어떤 인접리스트를 탐색해야 할지 생각이 필요한것 같다. 처음 문제를 보았을때 인접리스트를 바로 떠올리지는 않았다. 유니온-파인드인가..?? 생각을 해봤는데 아닌것 같았고.... 뭔가 다음 노드로 이동할때 마다 이동한 노드의 부모 노드를 표시해줘야 할것 같은데 한참을 생각하다가 인접리스트를 이용한 완전 탐색을 떠올렸다. 문제의 예제를 인접리스트와 그래프로 표현하면 다음과 같다. 이제 그래프 완전 탐색을 하면서 현재의 노드의 부모가 어떤건지 표현해주면 된다. 여기서 주의할 점은 단순 dfs로 문제를 풀때 이미 탐색이 끝난 노드는 재방문 하지 않돌고 visit..

이 문제는 기본적인 DFS를 활용한 땅 갯수 구하기와 비슷한 문제이다. 문제에서 정상인이 보이는 색과 적록색약이 보이는 색이 다르다. 따라서 각각 정상인 경우와 적록색약인 경우로 나누어 각각 DFS를 돌리면 된다. #include #include #include #include using namespace std; char rgb[102][102]; char rb[102][102]; bool visited[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; int n; int rgbCnt = 0, rbCnt = 0; void dfs(int x, int y, char arr[][102],char c) { if(visited[x][y]) { ret..

우선 이 문제는 그래프 문제로 N 개의 정점이 주어지고 M개의 연결이 주어질때 '모든 정점'에서 '모든 정점'으로의 최단경로를 구하는 문제이다. 플로이드 와샬 알고리즘을 알고 있었다면 간단하게 해결할 수 있는 문제이다. 하지만 플로이드 와샬 알고리즘을 몰랐기 때문에 인접리스트를 이용하여 DFS로 문제를 해결하였다. 각 정점에서 다른 정점까지 최단 경로를 구해야 하기 때문에 생각해낸 방법은 리스트에 찾고자 하는 정점이 있을경우 1번에 탐색 가능, 없을경우 리스트에 있는 정점으로 이동하여 다시 탐색하는 방법을 사용하였다. 어찌어찌 이상한 방법으로 문제를 해결하였지만 알고리즘 분류를 확인하고서 플로이드 와샬이라는 것을 알게 되었다. 우선 내가 푼 방법을 공유하고 다시 플로이드 와샬로 문제를 풀어보도록 하겠다...

이 문제는 이전에 풀었던 문제와 입력 방식만 다른 완전히 같은 문제이다. https://devconf.tistory.com/40 BOJ 1967 트리의 지름 문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드 devconf.tistory.com 기본적인 방식은 특정 아무 위치에서 DFS를 통해 길이가 최대가 되는 시작점을 구하고, 그 시작점에서 다시한번 DFS를 돌리면 된다. #include #include #include #include using namespace std; int v; vector adj[100001]; bool visited[100001]; int ..

문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드에서 가장 깊이 들어가야 최소한 최대 길이가 될것 같다는 생각을 하였다. DFS를 생각한것이다. 하지만 DFS 한번만으로 도저히 답을 찾아낼 수 없었다. 풀이를 보니 DFS를 두번 사용 해야 한다고 하였다. 왜 DFS를 두번 사용해야 하는지 이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다. 하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다. 즉 어느 점에서 DFS를 통해 가장 긴 점을 찾으면 그 점은 가장 지름이 긴 원의 시작 점이 된다. 이후 그 시작점에서 또 가장 긴..

물의 높이가 0~100 까지 변하는 동안 각 높이마다 잠기지 않는 안전한 영역이 존재한다. 문제 해결 방법은 각 높이에서 안전한 영역의 최대 갯수를 구하는 것이다. 안전한 영역 즉 섬의 갯수를 구하기 위해서 물의 높이보다 높은 영역을 기준으로 DFS를 적용하였다. 핵심은 방문한 영역을 표시 하고 한번 방문한 영역은 DFS에서 제외시켜야 한다. #include #include #include using namespace std; int n; int map[102][102]; bool visit[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; void dfs(int x, int y, int height) { if(visit[x][y]) { re..