[백준] 17142.연구소3 (java) / 조합, BFS
@조합, BFS / 45m 이번이 3번째 풀이 무난한 문제인데, 조건 하나때문에 틀려서 다시 풀었다. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 세달 전에도 풀었던 문제인데, 그때도 삽질하고 지금도 삽질..ㅎㅎ 이전 풀이 https://buddev.tistory.com/34 [백준] 17142.연구소3 (java) / 백트래킹, DFS, BFS, 조합 @백트래킹, DFS, BFS, 조합 / 43m (필기 11분, 디버깅 8분 포함) 기본..
2020. 5. 30.
[백준] 17142.연구소3 (java) / 백트래킹, DFS, BFS, 조합
@백트래킹, DFS, BFS, 조합 / 43m (필기 11분, 디버깅 8분 포함) 기본 문제인데 조건을 하나 놓쳐서 그 부분 고치고 무난하게 풀었다. 문제 링크 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는..
2020. 2. 25.
[백준] 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.
[백준] 16637.괄호 추가하기 (java) / DFS, 백트래킹, 조합, 시뮬레이션
@DFS, 백트래킹, 조합, 시뮬레이션 / 3h 이상 간단한 문제라고 생각했는데, 조합에서 한번 헤매고, 계산하는 곳에서 한번 더 헤매서 처음 맞았을때는 도대체 왜 맞는지도 이해가 안됐었다. 재귀를 이용한 DFS 백트래킹 조합을 공부하는 기회가 됐다. 구현 방법 DFS, 백트래킹을 이용한 조합 구현 1. 괄호를 놓을 수 있는 곳은 3+ 8* 7- 9*2 이 네 곳(== 배열크기 N / 2)이다. 그런데 빨간 칸에 연속해서 괄호를 배치할 수는 없으므로, 괄호 개수를 0부터 - 가능한 최대 개수 까지 놓되, 인접한(붙어있는) 칸은 뽑지 않는 조합을 구하기로 했다. 2. 그런데 이 조합을 구하는게 생각보다 너무 어려워서, 결국 실패하고 도움을 받았는데, 바로 이 방법이다. (더 나은 방법은 4번 참고) 1) ..
2020. 2. 10.
