BFS4 [C++] 백준 2638 - 치즈 (직관적인 접근) 백준 2638 : 치즈 난이도 : 골드 3 시간 : 1시간 20분 소요 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 과정 이 문제는 bfs를 사용하는 것이 유리하다. 이 문제를 봤을 때, 가장 중요하다고 생각했던 것은 내부와 외부를 구별하는 것이었다. 내부와 외부가 구별되지 않는다면 접하는 4개의 면이 0인지 아닌지만 판단하면 되기 때문이다. 정의 ch[MAX][MAX] : 치즈값을 저장하는 2차원 배열, 상태에 따라.. 2023. 3. 3. [C++] 백준 10026 - 적록색약 백준 10026 : 적록색약 난이도 : 골드 5 시간 : 17분 소요 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 과정 bfs를 사용하면 쉽게 풀 수 있는 문제이다. 적록색약인 경우와 아닌 경우를 구별하기 위해 2개의 함수, 2개의 2차원 배열을 사용했다. 적록색약이 아닌 경우에는 방문하지 안한 rgb를 방문하여 인접 노드가 같은 색일 때만 방문처리하고, 큐에 넣는다. bfs1 함수는 방문하지 않은 노드일 때만 실행되기 때.. 2023. 3. 1. [C++] 백준 1707 - 이분 그래프 백준 1707 : 이분 그래프 난이도 : 골드 4 시간 : 1시간 소요 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 과정 bfs를 사용해서 풀 수 있는 문제이다. 초기에는 2차원 배열로 풀어볼까 생각했지만 입력값의 크기가 2만이라 2차원 배열을 만들면 제한 용량을 넘긴다. 그래서 vector board[MAX] 로 1차원 배열로 벡터를 만들어서 구현했다. 먼저 입력 t1,t2를 받으면 t1,t2 배열에 각각 저장한다. 그 후 1번.. 2023. 3. 1. [C++] 백준 7576 - 토마토 백준 7576 : 토마토 난이도 : 골드 5 시간 : 50분 소요 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 과정 어떤 식으로 풀어야 할지는 금방 생각했지만 구현하는 것이 오래걸렸다. 해결 방법은 먼저 시작점(익은 토마토)를 순차적으로 찾은 후, 시작점에서 익힐 수 있는 토마토들을 큐에 넣는다. 그 후 큐가 비어질 때까지 큐에 있는 모든 토마토를 방문하면 된다. x, y 좌표와 날짜를 저장하는 자료형이 필요했지만.. 2023. 2. 28. 이전 1 다음
