본문 바로가기

백준/그래프83

백준 2638 c++ "치즈" -[PlusUltraCode] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [필자 사고] BFS 탐색 문제다. 이 문제의 핵심 풀이는 외부 공간과 치즈 내부 공간을 구별해야 된다. 인덱스 0,0은 확정적인 외부공간이므로 BFS탐색을 이용해 외부 공간을 방문처리를 해준다. 다음으로 치즈가 있는 곳에서 외부공간과 접촉한 갯수가 2개 이상인 경우 배열을 변경해주면 풀이는 완성이다. [소스코드] #include #include #include using namesp.. 2024. 3. 7.
백준 2146 c++ "다리 만들기" -[PlusUltraCode] https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [필자 사고] BFS탐색문제이다. 먼저 각 섬을 고유의 번호로 분리 시켜야 한다. 필자는 한번의 BFS 탐색을 이용해 분리시켰다. 다음으로 고유의 땅과 바다가 인접한 sero와garo 인덱스들을 찾아 최단거리 알고리즘을 이용하여 전체 탐색 해주었따. 시간복잡도를 계싼해보면 O(N^3logn) 으로 생각이 든다. [소스 코드] #include #include #include using namespace .. 2024. 3. 6.
백준 1926 c++ "그림" -[PlusUltraCode] https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net [필자 사고] 이 문제는 BFS탐색 알고리즘을 이용하면 쉽게 풀 수 있다. 특이한 점은 1과 0의 구역을 구별하는게 핵심 포인트다. [소스 코드] #include #include #include using namespace std; int N, M; vector Arr; vector visited; void Input() { cin >> N >> M; Arr.resize(N); visited.resiz.. 2024. 3. 5.
백준 2636 c++ "치즈" -[PlusUltraCode] https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net [필자 사고] 이 문제는 BFS탐색 알고리즘을 사용하면 해결할 수 있는 문제이다. 특이한 점은 치즈의 안과 밖을 구분해야 된다는 점이다. 처음에는 2번의 BFS를 이용하여 안과 밖을 구분하겠다 생각 했지만 1번의 BFS만으로 안과 밖을 구분할 수 있던걸 깨닫고 코드로 만들었다. [소스 코드] #include #include #include using namespace std; typedef struct Cheeze .. 2024. 3. 5.

티스토리툴바