본문 바로가기

dfs10

[백준] 2468.안전 영역 / DFS @DFS / 22m (필기 5m) 조건이 헷갈려서 4-5번 틀렸다. edge case에 대해 조금 더 깊게 생각해보는 습관 필요 문제 링크 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 삽질 포인트 1. 높이가 1~100 이므로 비가 오는 높이의 for문을 1-100까지 돌려야 하는데 이때 머리를 쓴다고 비가 1만큼 오면 어차피 다 잠기니까 안전영역이 0개가 되고, 비가 100만큼 오면 하나도 안 잠기니까 안전영역이 1개가 된다고 생각해서 2-9.. 2020. 9. 6.
[백준] 17779.게리맨더링2 (java) / BackTracking, DFS, 시뮬레이션, 완전탐색 @BackTracking, DFS, 시뮬레이션, 완전탐색 / 4h 이상 (디버깅만 3시간 한 듯) SWEA 2105.디저트 카페 ( 포스팅 ) 와 비슷한 문제처럼 보여서 쉽겠거니 하고 풀었는데, 테케조차 계속 틀리게 나와서 디버깅하느라 너무 힘들었다..ㅠ 풀고나서 다시 보니 너무 어렵게 생각했던 것 같다. 그래도 백트래킹 공부하기에는 좋은 문제인 듯.. 문제 링크 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정.. 2020. 3. 8.
[백준] 14502.연구소 (java) / 백트래킹, DFS, BFS, 조합 @백트래킹, DFS, BFS, 조합 / 29m (필기 15m 포함) 기본 문제라서 무난하게 풀었다. 문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 구현 방법 이 문제는 빈 칸.. 2020. 2. 25.
[백준] 14500.테트로미노 (java) / 백트래킹, DFS @백트래킹, DFS / 20m (6m 필기 포함) 예전에 두번 풀어봤던거라 풀이법을 알고 있어서 금방 풀었다(거의 외워서 푼 수준..ㅎ) 그렇지만 예전보다 더 간단하게 풀었다는 것에 의의를.. 문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려.. 2020. 2. 24.
[백준] 17136.색종이 붙이기 (java) / 백트래킹, DFS @백트래킹, DFS / 45m (필기 15m 포함) 예전에 두번 풀어봤을 때 두번 다 실패했었는데(설명 듣고도) 오랜만에 풀었는데 한번에 풀어서 뿌듯했다ㅎㅎ 문제 링크 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐 www.ac.. 2020. 2. 24.

티스토리툴바