그래프_탐색_이론

[C++] 백준 23288번 주사위 굴리기 2

23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제이다. 이해하기 어려웠고, 시간을 잡아먹었던(자꾸 8번째 테스트 케이스가 이상하게 나와서 고쳤다.) 것들이 있었다. 조건들을 정리해가면서 문제 풀이를 정리해 보겠다. 문제풀이 문제의 조건들을 정리해보면, 다음과 같은 순서로 구현하면 된다. 높이, 너비, 주사위 이동횟수를 입력받는다. 격자의 각 칸의 숫자를 입력받는다. 여기까지가 기본 입력이다. 그 후에 이동횟수만큼 아래를 반복..

[C++] 백준 2573번 빙산

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 구현 / 그래프 탐색 문제. 삼성 기출 문제와 유사한 문제였다. 문제에서 제시하는대로 구현하면 맞출 수 있는 문제다. 문제풀이 다음과 같은 순서로 만들면 된다. 0이 아닌 칸들에서 인접한 칸들 중 0인 칸들의 개수를 큐에 저장해둔다. 큐에 있는 정보를 토대로 각 칸마다 0인 칸들의 개수만큼 높이에서 빼준다. DFS / BFS를 통해 연결 요소의 개수를 구해서 2 이상인 경우에는 몇 년 걸렸는지 출력한다. 2 미만일 경우에는 1로 돌아간다. 이 때 DFS /..

[C++] 백준 12851번 숨바꼭질 2

그래프 탐색 문제. BFS 너비 우선탐색을 통해서 풀면 되는 문제다. 조건이 꽤 까다로운 문제다. 다른 그래프 탐색 문제들처럼 풀면 메모리 초과가 난다. 문제풀이 예전에 숨바꼭질1을 풀었었는데, 그 때는 그냥 가장 빠르게 목적지에 도달한 경우 몇 초인지만 알면 되는 문제였다. 이 문제는 가장 빠르게 목적지에 도달한 경우가 몇 초이고, 그 시간대로 가는 경우가 몇 가지가 존재하는지 출력하면 된다. 조건은 짜기 나름이므로, 코드 전문을 보고 틀린 이유만 정리하겠다. /* * 백준 12851번 숨바꼭질 2 * https://www.acmicpc.net/problem/12851 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include using namespace std; int s..

[C++] 백준 1068번 트리

그래프 탐색 문제. 그 중에서도 트리 & DFS문제이다. 트리의 기본 개념만 안다면 쉽게 풀 수 있다. 조건을 하나 잘못 생각해서 틀렸었다. 문제풀이 어려운 것 없이, 부모 - 자식, 자식 - 부모 관계를 모두 저장해둔다. 그리고 각각 다음에 사용한다. 부모 - 자식 관계 : 트리에서 깊이 우선 탐색을 통해 리프 노드가 몇 개인지 구할 때 사용한다. 자식 - 부모 관계 : 지울 노드의 부모 노드의 번호를 구하고 해당 부모 노드에서 부모 - 자식 관계에서 지울 노드를 찾은 후 지울 때 사용한다. 루트 노드가 예시 케이스에서는 -1이 모두 첫번째로 나오긴 했지만, 나중에 나오는 경우를 대비해서도 코드를 구현했다. /* * 백준 1068번 트리 * https://www.acmicpc.net/problem/10..

[C++] 백준 5014번 스타트링크

그래프 탐색 중 너비 우선 탐색으로 푸는 문제. [C++] 백준 1107번 리모컨 브루트 포스 완전탐색 문제. 이 문제는 두 번 풀게됐는데, 처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서 백준 게시판을 참고해서 다시 풀게됐다. 정답 비율이 낮지 kimyunseok.tistory.com 위 리모컨 문제와 똑같은 문제였다. 예전에 푼 로직이 생각나서 바로 풀 수 있었다. 문제풀이 리모컨 문제와 아주 유사한 문제이다. BFS를 하게 되는데, 현재 층에서 위, 아래 층이 유효한 층이고 방문하지 않았다면 다음 층을 큐에 넣어주면서 계속 탐사하게 구현하면 된다. /* * 백준 5014번 스타트링크 * https://www.acmicpc.net/problem/5014 * 그래프 탐색 이론 ..

[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름 그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다 kimyunseok.tistory.com 위 문제와 거의 똑같은 문제. 차이점이라면, 루트 노드가 1이 아니다. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다. -1이 나오기 전까지 노드를 연결시킨다. 정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다. 위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다. 문제풀이 자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.) 우선, 루트 노드가 무엇인..

[C++] 백준 17142번 연구소 3

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 골드 4 문제이며 연구소 문제의 후속작(?)인 것 같다. 연구소 문제는 골드 5에 정답률도 55%를 기록하고 있지만, 이 문제는 골드 4에 정답률이 25%를 기록하고 있다. 연구소 문제는 그래프 탐색 이론 문제이고, 너비 우선 탐색(BFS)을 통해서 푸는 문제이다. 사실 왜 맞았는지 잘 모르겠다. TC들이 제대로 나오지 않길래, 조건을 조금 수정해서 TC들이 잘 나와서 제출했더니 맞았습니다!! 가 나와버렸다... 한번 글..

[C++] 백준 4179번 불!

그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 아예 조건이 똑같던 문제였는데 불! 문제는 풀었었다. (오히려 정답률은 탈출이 높다..뭐지..?) 다른 사람들 풀이를 보니 조금 쉽게 접근한 거 같았다. 시간도 내가 훨씬 많이 걸리고 있었다. 다른 사람들 코드를 봐도 크게 다른 점은 못 찾았다. 아마 priority_queue를 custom해서 쓰는데, 이게 문제인 것 같았다. queue 자료구조만 사용해서 풀어도 풀 수 있는 문..

[C++] 백준 16236번 아기 상어

구현 / 시뮬레이션 + BFS(너비 우선 탐색) 문제. 테스트 케이스가 상당히 많고 잘 돼 있어서 디버깅을 하다보면 맞출 수 있다. 처음에 4번째 테스트 케이스가 자꾸 다른 값(60이 아니라 56)이 나와서 뭐가 잘못됐는지 모르겠어서 백준 게시판에 봤더니 고려해 주지 못한 부분이 있었다. 아마 테스트 케이스들만 올바른 방향으로 통과한다면 맞출 수 있을 것이다. 문제풀이 아기상어는 다음과 같은 조건을 갖는다. 이동은 상, 하, 좌, 우 방향으로 가능하다. 이동하는데는 1초의 시간이 소요가 된다. 처음 아기상어의 크기는 2이고 자신의 크기만큼 물고기를 먹으면 크기가 증가한다. 자신의 크기보다 큰 물고기가 있는 곳은 지나가지 못하고, 같은 물고기가 있는 곳은 지나가기는 가능하며, 더 작은 물고기가 있는 곳은 ..

[C++] 백준 2206번 벽 부수고 이동하기

그래프 탐색 문제. 최단 거리를 탐색하는 문제로, BFS를 응용해서 풀면된다. 조건을 따지지 못해서 검색을 했는데, 코드를 약간 수정해서 맞출 수 있었다. 처음에 이 문제를 접근했을 때 N x M의 맵이고, 벽은 1이고 땅은 0이다. 그리고 상, 하, 좌, 우를 이동할 수 있다. 1로 된 곳 중 하나를 부숴서 갈 수 있다. 나는 다음과같은 조건들을 고려했다. BFS로 점들을 이동하며, 내가 이 점에 왔을 때 벽을 부수고 온 것인지 아닌지를 고려했다. 만일 이전에 벽을 부수고 왔다면, 이번 정점에서는 벽을 가지 못하도록 했다. 이전에 벽을 부순적이 없다면, 벽을 부쉈다는 것을 기록하고 해당 벽을 방문한다. visit 2차원 배열을 만들어서 해당 지점을 방문한 것을 저장했다. 빨간색으로 칠한 이유는 저 부분..