본문 바로가기

dfs2

[백준] 14500번 테트로미노 - C++ 테트로미노 N x M 크기의 보드에 정사각형 4개로 이루어진 블록을 무작위로 배치했을 때 블록에 가려진 정수의 합이 가장 큰 경우의 값을 찾는 문제입니다. 어떻게 풀어야 하나.. 고민하다가 아이디어가 당장 안 떠올라서 노가다 - 멋있는 말로 브루트 포스 - 로 풀었습니다.풀이방법 그림과 같이 엑셀에 모든 블록의 경우의 수를 정리해 보니까 19가지의 블록을 최대 500 x 500의 보드에 배치하는 것이기 때문에 시간제한 2초 안에 성공할 수 있을 것 같아서 브루트포스를 선택했습니다. 그림과 같이 블록들을 가로 x 세로의 크기대로 분류하면 총 5가지의 유형으로 분류할 수 있습니다. 유형별로 2중 for문을 돌리고 for문 안에서 공통된 블록은 한 번만 계산함으로써 최대한 연산을 줄였습니다.코드#include.. 2024. 11. 9.
[백준] 4963번 섬의 개수 - C++ 섬의 개수 문제 이름을 클릭하면 문제 설명을 볼 수 있습니다. 이번 문제는 0과 1로 이루어진 지도에서 섬이 총 몇 개 있는지 개수를 맞추는 문제입니다. 8방향으로 한 방향이라도 이어져 있다면 이어진 모든 섬을 한 개로 칩니다. 저는 2차원 배열을 순회하면서 DFS를 이용해서 해결했습니다.코드#include #include int main(){ std::cin.tie(NULL); std::ios::sync_with_stdio(false); std::pair dir[8] = { {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} }; while (true) { int w, h; std::cin >> w >> h; if (w == 0 && h .. 2024. 8. 30.

티스토리툴바