본문 바로가기
728x90

백준브실골/Graph13

백준 11112, Eight puzzle 개요 문제 링크 골드 1, Graph, BFS 격자퍼즐을 풀 수 있는 최소 시행 횟수 구하기 접근 퍼즐형 BFS, 1525의 심화버전이다. 1525를 풀때는 나도 string을 썼는데, 이번에는 int를 써서 해결해봤다. 방법은 크게 복잡하지 않다. 빈공간의 주변의 2-4개 점을 다음점으로 하고, cnt+1해서 queue에 넣어 BFS를 돌리면 된다. 그런데 문제는 이게 100개의 데이터에 대해 전부 다 BFS를 돌려버리면 시간에서 터진다는 것이다. 그래서 해결법은? 정답부터 시작해서 전체 가능한 경우의 count를 전부 저장해버린다. 즉 완탐을 한 번 돌리고 들어가는 것이다. 이게 사실 문제의 핵심이고 나머지는 1525와 다를게 없어서 안된다면 1525부터 풀어보는 것이 좋다. string을 int로 .. 2023. 5. 12.
백준 3665, 최종 순위 개요 문제 링크 골드 1, Graph m개 쌍의 전후관계가 바뀔 때 다른 쌍의 전후관계를 유지하며 변경 가능한지 출력하기 접근 그래프의 개념이나 수학적 센스를 기르기 매우 좋은 문제. 우선 출력조건을 잘 보면 순위를 찾을 수 없는 경우 "?"를 출력하라고 나와있는데, 순위를 찾을 수 없는 경우는 존재하지 않는다. 왜인지가 쉽게 생각되지 않는 이유는 "데이터에 일관성이 없다" 라는 말이 전혀 이해가 안되기 때문인데, 세 번째 테케를 이해하는 것부터 해보자. [1 2 3 4]에서 1,2 앞뒤가 바뀌고, 2,3, 3,4 바뀌면 엥 [4 3 2 1]이면 되는거 아님? 하고 생각할 수 있다. 하지만 핵심은 저 세 가지 바뀌는 관계 외에, 원래 존재하던 나머지 세 개 (1,3 / 1,4 / 2,4)의 전후관계가 유.. 2023. 5. 12.
백준 21940, 가운데에서 만나기 개요 문제 링크 골드 4, Graph 주어진 점으로부터의 거리의 최댓값이 최소가 되는 지점 접근 전형적인 플로이드 워셜 문제, 다익스트라를 써도 되겠지만 한점->여러 점의 경로를 구하는 것이 아닌 여러점-> 여러점의 경로를 구하는 문제이고, N이 200으로 작으니까 플로이드 워셜로 완전탐색을 해주면 된다. 플로이드 워셜은 중간점을 잡는 방법이라고 생각하면 쉽다. i부터 j로 이동할 때 어떤 중간점을 경유해서 가는 것이 이득이면 업데이트 해준다. 마지막으로 단방향 경로가 제공되므로 기준점 s에 대해 (s,i)+(i,s)의 거리를 기준으로 업데이트 하면 된다. Pseudo code adj = {1e8} // 최댓값으로 초기화 // 두 값의 합이 int 범위 내에 있어야하니 1e9이내로 for (m) adj[.. 2023. 5. 12.
백준 18224, 미로에 갇힌 건우 개요 문제 링크 골드 1, BFS 밤에만 벽을 넘으며 끝점까지 이동하는 방법 접근 왜 건우는 미로에 갇혀 우리를 괴롭게 만들까? 정답률 15%의 까다로운 문제였다. 우선 구조체 안에 모든 함수를 넣고 BFS를 돌려보자. 우선 문제가 까다로워 지는 이유는 시간개념 때문인데, 이렇게 이해해보면 쉽다. // M = 4 1 2 3 4 5 6 7 8 9 10 s s s s m m m m s s 1 1 1 1 1 1 1 1 2 2 이렇게 sun과 moon이 번갈아서 있고, day는 2*M마다, 낮밤은 M 마다 바뀌게 된다. 그래서 이동 횟수를 D라 할 때, 낮밤은 1-D/M%2, 일수는 1+D/M/2로 구하게 된다. M마다 일 수가 바뀌는 것이 아니라 낮밤이 바뀌기 때문에 이게 문제 해결과정에서 엄청 헷갈린다. 다.. 2023. 2. 23.
백준 13459, 구슬 탈출 개요 문제 링크 골드 1, BFS 보드를 회전하여 파란공이 아닌 빨간 공만 구멍으로 통과시키는 방법 접근 C언어로 꽤 오래 고민하다가 예제도 못풀어서 포기했던 문제인데 C++로 2트만에 풀었다. C++은 역시 미쳤다. 번거롭게 이런저런 함수를 짜지 말고 구조체 내에서 전부 해결하자. 구조체에는 빨간공과 파란공의 위치를 저장하자. 테두리에 벽이 쳐져있다 했으니 밖으로 나가는 건 고려하지 않아도 된다. 벽이냐, 구멍이냐만 판단한다. 이동하는 것도 구조체 내의 함수로 해결하자. dy, dx를 이용하고, 다음 이동할 점의 조건에 따라 다음과 같이 판단한다. 만약 다음점이 벽이면 이전점을 내보낸다. (더 이동하지 않는다.) 만약 다음점이 구멍이면 다음점을 내보낸다. 만약 파랑의 다음점이 빨강이고 빨강이 구멍에 없.. 2023. 2. 23.
백준 17089, 세 친구 개요 문제 링크 골드 5, Graph 서로 연결된 세 점을 골라 세 점 사이 연결선이 아닌 다른 연결선의 개수의 합의 최솟갑 구하기 접근 그래프 이론이라 하기에도 애매한 문제. 인접행렬을 이용하면 쉽게 풀린다. 두 사람의 연결 여부를 arr[a][b]와 같은 식으로 저장하고, 연결 개수를 미리 저장해 TLE를 방지한다. 그리고 3명의 연결개수 합 - 6의 최솟값을 구해주면 된다. Pseudo code for (m) arr[a][b] = 1, arr[b][a] = 1 count[a]++, count[b]++ for (i) for (j) if (!arr[i][j]) continue for (k) if (!arr[j][k]) continue if (!arr[k][i]) continue ans = min(cou.. 2023. 2. 23.
백준 1525, 퍼즐 개요 문제 링크 골드 2, BFS 빈칸과 다른칸의 자리를 바꾸며 3X3 퍼즐을 번호순으로 정렬하기 위한 최소 시행 수 접근 메모리 제한이 빡세므로 좋은 자료형을 써야한다. 우선 BFS를 써야하니 방문체크와 queue를 써줘야 할텐데, 방문 체크를 어떻게 해줄지가 관건이다. 9개의 지점의 값과 0의 위치, 시행 수를 한 구조체에 저장해야 한다. 처음에는 {x,y} 구조체를 만들어서 저장해봤는데 아무리 해도 메모리 초과가 날 것 같았다. 주변 4개 점을 탐색하는 과정에서 다음점이 외부로 나가는 지 확인하는데, 이 과정에 시간도 많이 걸릴 것 같았다. 그래서 내 해결법은 string을 이용하고, 9개의 점에 대해 주변점의 좌표를 미리 저장한다. 그리고 map을 활용한다. 아마 C로 풀었으면 못했을 것이다. 그.. 2023. 2. 22.
백준 25515, 트리 노드 합의 최댓값 개요 문제 링크 골드 4, DFS, DP 루트노드부터 자식 노드들을 탐색하며 더한 특정값의 합의 최댓값 접근 DP는 내가 잘 못쓰겠고, DFS나 재귀를 이용해 풀어줬다. 우선 총 합이 10^10이 될테니 long long을 사용한다. 만약 자식노드가 없다면 현재 위치의 특정값을 반환한다. 자식노드가 있다면? 자식노드의 DFS가 0보다 크면 더해준다. 구현은 C++의 미친장점 vector를 이용해준다. 메모이제이션을 써봤는데 성능에 큰 차이가 없었다. 이유는 한 번 방문한 노드를 다시 방문하지 않기 때문이다. Pseudo code DFS(cur) { if (child[cur].length == 0) return value[cur] for (c = child) if (0 < DFS(c)) ret += DFS.. 2023. 2. 22.
백준 18500, 미네랄 2 개요 문제 링크 골드 1, BFS 왼쪽, 오른쪽 순서대로 벽을 부술 때 덩어리가 테트리스처럼 내려가게 만들기 접근 삼성 SW 역량테스트 느낌의 재밌는 구현 & 시뮬레이션 문제. BFS보다는 구현에 더 비중을 두긴 했다. 헷갈리는 구현이 많은데 핵심은 덩어리 그루핑이다. 덩어리 그루핑은 DFS와 재귀를 이용하는 방식이 익숙한데 TLE가 날 것 같아서 queue와 BFS를 써줬다. 덩어리, 즉 클러스터를 만든다. 클러스터는 내려갈 수 있는 한 최대한 내려가면 된다. 내려가는 조건은? 아래 점에 클러스터가 없으면 된다. 이때 1열에 내리고자 하는 클러스터가 있으면 반드시 안된다. 내릴 수 있을 때까지 내려야 하므로 내리기는 while문을 이용해야 하는데, 위에서 설명한 조건을 출력해주면서 실행하면 보다 단순하.. 2023. 2. 21.
백준 1245, 농장 관리 개요 문제 링크 골드 5, BFS, DFS 한 칸 패딩된 주변 점들에 비해 높이가 높은 같은 높이의 덩어리 개수 구하기 접근 조건이 많이 까다로운 경로탐색 문제. 문제를 잘 읽지 않으면 틀리기 매우 좋다. 우선 예제부터 풀어보자. 8 7 # 3 2 2 1 0 # 3 3 3 2 1 0 # 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 # # 1 1 0 0 1 1 1 # 1 0 봉우리는 이렇게 세 부분이다. 한 칸 패딩된 주변 점들에 비해 높이 있어야 한다. 패딩이 무슨 말인지 헷갈린다면 테두리를 그린다고 생각하면 쉽다. 그리고 모든 점의 높이가 같아야 한다. 연결할 때는 대각선끼리의 연결도 유효하고, 이렇게 덩어리 진 것들의 개수를 구해주면 된다.. 2023. 2. 20.
728x90

티스토리툴바