전체 글
4963번-섬의 개수
문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 접근방법 1) 접근 사고 1. 섬을 8가지 방향으로 탐색을 합니다. 2. 탐색을 하면서 방문한 섬은 visited배열을 사용해서 방문 체크를 진행해줍니다. 3. 시도한 BFS 횟수가 섬의 개수를 의미하는것을 알 수 있습니다. 2) 시간 복잡도 O(V + E) 3) 실수 r과 c의 위치가 바껴서 나온다. 문제 설명이 너무 불친절한거 아닌가.. 예제를 다시 보고 입력 부분이 잘못되었다는것을..
11724번-연결 요소의 개수
문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 접근방법 1) 접근 사고 1.연결 요소의 개수를 구해주면 되기 때문에 방문한 노드 지점을 visited 배열을 사용해 체크해줍니다. 2. 방문한 지역은 visited를 사용해 제외해주었기 때문에 DFS 시도횟수의 의미가 전체 연결 개수의 의미를 의미하므로 DFS 시도 횟수를 출력해줍니다. 2) 시간 복잡도 O(V + E) 3) 실..
1012번-유기농배추
문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 접근방법 1) 접근 사고 문제를 읽고 해석해보면 배추가 있는 구역인 1부분을 탐색하면 해결되는 문제였습니다. 2) 시간 복잡도 O(V + E) 3) 실수 fill을 사용할 때 열만 +1하면 되는데 행까지 +1을 해서 outofmemory오류가 발생하였다. 4) 배운점 5) PS 정답코드 #include using namespace std; int t, r, c, ea; const int MAX = 50;..