DFS

[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다. 위 그래프는 2개로 나눌 수 있다. 위 그래프는 하나로 연결된 하나의 그래프이다. 모든 노드는 BFS 탐색의 시작점이 될 수 있다. BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다. 시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다. 개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다. 최종 코드 #include #include #include using namespace std; vector adj[201]; bool visited[201]; void bfs(int start){ queue que; que.push(start); visited[start..

[프로그래머스] level2 빛의 경로 사이클 (C++)

월간 코드 챌린지 시즌 3 그림만 보면 무시무시하지만 실제 풀이는 그렇지 않다. 하나의 격자에 빛을 쏘면 내부에서 사이클을 이룬다. 내부에서 퍼지는 게 아니라 하나의 길로 쭉 들어간다고 생각해서 바로 dfs로 풀었다. bool cache[501][501][4]; cache 배열이 중요하다 cache[r][c][dir] r, c 의 격자에 dir 방향으로 들어온 적이 있는지를 체크하는 배열이다. 나는 dir 방향으로 들어온 적이 있다면 반드시 그 경우에 해당하는 사이클이 존재한다고 생각했다. 적어도 위 예제만 봐도 모든 경로를 다 탐색한다. 만약 다른 예제가 오더라도 아직 방문하지 않은 경로를 시작점으로 탐색을 하는데, 이미 탐색한 다른 경로를 건드릴일이 절대로 없다는 것이다. bool &ret = cac..

[프로그래머스] level2 거리두기 확인하기

단순 bfs, dfs 문제이다. 최대 2칸까지 이동할 수 있다. 다음 칸이 'X'인 경우 이동하지 않는다. 다음 칸이 'P'인 경우 거리두기가 지켜지지 않은 것이므로 false를 반환한다. bfs로 풀면 queue의 각 원소가 현재 몇 칸 움직인 상태인지 저장해두는 작업이 필요해서 queue를 구성하는 struct를 새로 구현하게 되었다. #include #include #include #include #define pii pair using namespace std; struct Info{ pii now; int cnt; }; int dr[4] = {0, 0, 1, -1}; int dc[4] = {1, -1, 0, 0}; int Map[6][6]; bool check(int r, int c){ queu..

[백준 1043] 거짓말 (C++)

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 재미있는 문제였다. 나는 사람과 파티를 똑같이 하나의 정점으로 보았다. 둘다 최대 50이므로 사람은 51부터, 방은 1부터 번호를 가지도록 설정했다. 진실 감별사부터 시작하는 dfs를 수행한다. 이때 연결되는 모든 정점은 진실 감별사로 바뀌게 된다. 처음 주어진 진실 감별사와 연결된 모든 정점을 진실 감별사로 바꾸고, 아직까지 진실 감별사가 되지 않은 사람의 수를 출력하면 답을 구할 수 있다. 처음에 Union find로 풀려고 했다가 너무 어려워졌다. 그래프를 계속 그려..

[백준 1199] 오일러 회로(인접 리스트) (C++)

[백준 1199] 오일러 회로 C++ 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 hyeo-noo.tistory.com 예전에 풀었던 오일러 회로 문제가 인접행렬로 풀 수 없게 데이터가 추가되면서 많은 사람들이 시간초과의 늪에 빠졌었다. 나도 마찬가지로 시간초과로 틀리게 되었고 4달이 지나서야 인접 리스트 방식의 오일러 회로를 공부하고 다시 풀게 되었다. INPUT 우선 input 부분에 많은 변화가 있었다. i에서 j로 가는 간선을 인접 행렬로 저장하지 않고 간선 그 자체로 저장했다. 대신에 j에서 i로 가는 간선은, 입력에서 i에서 ..

[백준 16437] 양 구출 작전 (C++)

16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 각 마을에 있는 늑대와 양의 수를 island 배열에 저장한다. 이때 늑대의 수는 음수로 저장하도록 했다. 양이 1번 섬으로 들어오는 최대 수를 알아야 한다. 따라서 1번 섬에서 시작해서 양을 데려온다는 생각으로 dfs를 수행했다. 1. 만약 현재 섬이 리프 노드이고 양이 살고 있다면 양을 데리고 올 수 있다. return 양의 수 만약 현재 섬이 리프 노드이고 늑대가 살고 있다면 0을 리턴한다. 2. 현재 섬에 살고있는 양 또는 늑대(음수)를 ..

[백준 16197] 두 동전 C++

16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net DFS, BFS 1. 문제 해결 아이디어 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다. 문제에 나와있는 그대로 구현했다. DFS를 통해서 잘못된 길에 들어선 뒤에 백트래킹이 가능하게 구현을 하였다. memset(Map..

[백준 1199] 오일러 회로 C++

1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net DFS, 오일러 1. 문제 해결 아이디어 오일러 서킷 오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접 hyeo-noo.tistory.com 이 문제는 오일러 서킷을 구하는 문제이다. 위 링크의 알고리즘에 따라서 구현을 하고, 간선정보를 받은 후 정점에 대한 degree가 홀수인 정점이 존..

오일러 서킷

오일러 서킷 : 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로 -> 한붓그리기 그래프의 시작점을 u, 끝점을 v라고 하자 1. u != v 인 경우 : v는 항상 홀수 개의 간선과 인접한다. v를 지나기 위해서 v로 들어가는데 하나, 나가는데 하나가 필요하다. 만약 v가 끝점이라면 v로 들어가는 간선에 대응하는 나가는 간선이 없다는 뜻이므로 v에 인접한 간선의 수가 홀수 일 수밖에 없다. 2. u == v 인 경우 : v는 항상 짝수 개의 간선과 인접한다. u에서 나가는 것으로 시작했기 때문에 u로 다시 들어왔다면 u(=v)에 인접하는 간선의 수는 짝수이다. 한 정점에 인접한 간선의 개수를 degree라고 하자. 오일러 서킷은 모든 정점에 들어가는 횟수와 나가는 횟수가 같아야하므로..

[백준 1405] 미친 로봇 C++

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 백트래킹 1. 문제 해결 아이디어 로봇이 최대 14번 움직이므로 14번 동안 자유롭게 움직일 수 있는 좌표 Map[32][32]를 설정해주었다. 초기 좌표를 적당한 중간 좌표로 잡아주고 백트래킹 dfs를 해준다. 움직일 때마다 확률을 곱해줘야 하므로 함수의 인자로 초기값 1을 가지는 확률 변수를 넘겨준다. 이동 중에 방문했던 곳을 다시 들리게 된다면 지금까지 곱해진 확률을 결과값에 더해준다. (단순하지 않을 때만 더해 줌) 결과는 단순한 경우를 찾으므로 1-..