코딩 공부하는 코딩류

배추밭에 필요한 배추흰지렁이의 최소 갯수를 구하는 문제 문제의 조건 1. 배추를 해충으로부터 보호하기 위해 배추밭에 배추흰지렁이를 놓을 것이다. 2. 지렁이는 상하좌우에 인접한 배추에게 이동할 수 있다. 3. 배추는 한 번에 많이 몰려있지 않고 밭 전체에 퍼져서 심어져 있다. 아파트 단지처럼 배추도 단지별로 심어져 있음 4. 필요한 지렁이의 최소 갯수 구해서 출력하기 5. 테스트 케이스가 여러 개 주어질 수 있다. 풀이 과정 1. BFS로 배추밭을 탐색하는데 전체 밭을 탐색해야 하기 때문에 2중 for문으로 [0, 0]번째부터 탐색한다. 2. 배추 한 칸을 대상으로 상하좌우에 또 배추가 있는지 검사해서 연결된 배추가 있으면 다음에 방문할 큐에 추가 3. 하나의 배추 단지 검사가 끝나고 나면 정답 카운트를..

서로 연결되어 있는 컴퓨터 중에서 바이러스에 감염된 컴퓨터가 몇 개인지 구하는 문제 문제의 조건 1. 컴퓨터의 갯수 N, 서로 연결된 쌍 M개가 주어진다. 2. 1번 컴퓨터는 바이러스에 걸렸는데 이 바이러스는 네트워크를 통해서 전파된다. 3. 1번 컴퓨터부터 시작해서 서로서로 연결되어 있는 컴퓨터들은 연결된 컴퓨터에게서 바이러스가 옮았다. 4. N개의 컴퓨터 중에서 1번 컴퓨터를 빼고 몇 개의 컴퓨터가 바이러스에 걸렸는지 출력 풀이 과정 쉽게 생각하고 시작했는데 생각보다 오래 걸린 문제 ㅠ.ㅠ 아직 dfs/bfs가 완벽하지 않아서 그런가 봅니다. 단순하게 모든 정점을 탐색하는 코드는 쉽게 짤 수 있지만 조금만 응용되어 나오면 방문할 필요가 없는 정점을 어떻게 거르나 고민하면서 시간을 많이 썼습니다. 풀이..

전형적인 BFS 문제로 정사각형 맵에서 연속되어 붙어 있는 집(1)들의 덩어리 갯수와 덩어리 안에 집이 몇개나 들어있는지 구하는 문제 문제의 조건 1. NxN 크기를 가진 정사각형 2차원 배열이 주어진다. 2. 2차원 배열에는 0과 1이 들어있다. 0은 아무것도 없는 곳을 뜻하고 1은 집이 있다는 것을 나타낸다. 3. 1들이 상하좌우로 연속해서 붙어 있으면 같은 단지로 친다. 주어지는 2차원 배열에는 단지가 여러개 있다. 4. 첫 번째 줄에 주어진 2차원 배열에 들어 있는 단지의 갯수를 출력하고 두 번째 줄부터 각 단지 안에 있는 집의 갯수를 오름차순으로 정렬해서 출력하기 풀이 과정 DFS 카테고리에 있긴 했지만 BFS로 풀어도 될 거 같아서 큐를 이용해 BFS로 풀었습니다. 한 타일을 기준으로 상하좌우..

아주 전형적인... BFS로 최단 거리를 찾는 문제 문제의 조건 1. N x M 크기의 미로가 주어진다. 2. 미로의 [1, 1]에서부터 [N, M]까지 가는 최단 거리를 구해서 출력하기 => 미로 배열의 [0, 0]에서부터 [N-1, M-1]까지의 최단 거리를 구하면 된다. 풀이 과정 많이 보던 스타일이라 낯설진 않았고 BFS 알고리즘도 어느정도 익숙해서 금방 풀 수 있을 것이라 생각했지만... 여전히 백준 문제의 입력을 받는 것에 익숙하지 않았기 때문에 입력을 받는 과정에서도 착오가 있었고... 최단 거리를 구하는 식을 잘못 썼고... 등등의 이유로 오래 걸린 문제입니다. ㅠ.ㅠ 그래도 덕분에 이젠 확실하게 알겠습니다... 근데 문제에 입력되는 숫자가 붙어서 주어진다 이런 말 말고 string형 배열..

제목 그대로 DFS와 BFS로 그래프를 탐색한 결과를 출력하는 문제 문제의 조건 1. 주어진 그래프를 DFS와 BFS로 각각 탐색한 결과를 순서대로 출력하면 된다. 2. 단, 방문할 수 있는 정점의 개수가 여러 개면 정점의 수가 작은 것 부터 방문한다. 풀이 과정 처음에는 요즘 알고리즘을 공부하고 있는 책에 나와 있는 알고리즘을 썼는데... (대충 엣지 좌우 저장하는 구조체 만들고 전체 그래프를 구성하는 클래스를 만든 뒤 그렇게 만들어진 그래프 클래스를 이용해서 bfs와 dfs를 수행하는 내용 코드 길이가 A4 한 장 정도 됨) 알고 보니 모든 정점이 서로서로 연결되어 있다는 것을 전제로 한 알고리즘이라 이번 문제에는 맞지 않았습니다. 주륵 ㅠ.ㅠ 그리고 제게는 그것을 수정할 능력이 없었습니다...ㅋㅋㅋ..

주어진 그림이 몇 개의 영역으로 나눠져 있으며 제일 넓은 부분은 어디인지 구하는 문제 문제의 조건 1. 그림의 세로 m, 가로 n, m x n 2차원 배열 picture가 주어짐 2. 주어진 그림에서 상하좌우 방향으로 연속한 숫자들만 같은 영역으로 침 -> BFS로 연속한 같은 숫자끼리의 넓이를 구하자 3. 영역이 몇 개인지, 그 중 가장 넓은 영역 크기는 몇인지 구하기 4. 전역변수는 solution 함수 안에서 초기화 해 주어야 함 #include #include #include using namespace std; int dir[4][2]; vector Pixels(pair curPos, int m, int n) { vector pixels; for (int i = 0; 4 > i; i++) { p..