dfs

Algorithm/BOJ
BOJ] 14502. 연구소
BOJ] 14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 2017년 SW역량테스트 기출문제 풀었던 문제지만, 떠올릴 겸 다시 풀어보았다. 생각보다 막힌 부분이 있었지만..
→2020.01.28
Algorithm/SWEA
SWEA] 2105. [모의 SW 역량테스트] 디저트 카페
2105.(모의 SW 역량테스트) 디저트 카페 2105. (모의 SW 역량테스트) 디저트 카페 문제의 저작권은 SWEA에 있습니다 대각선을 잘 그리면 되는 문제. 삼성공채 SW 역량테스트를 준비하기 전날에 풀까말까 하다가 안풀고 다른 구현문제를 풀었었는데, 이 문제를 풀고 시험을 봤다면 시간이 부족하지는 않았을텐데 라는 후회를 하게 만든 문제. 여하튼, 나중에 이 문제를 풀때 역시 2019 하반기 공채 삼성 SW역량테스트 오전 1번문제를 풀듯이 풀어봤는데, 생각보다 빡빡하고 시간도 오래걸렸다. (모든 경우의 수를 조건문으로 고려하는 구현방법으로 풀어서) 단순히, 방향과 프루닝(가지치기), 조건을 건 백트래킹을 사용하면 굉장히 파워풀하고 직관적이며 간단한 코드를 짤 수 있다. dfs 백트래킹 짱짱 혹시 비..
→2019.11.02
Algorithm/SWEA
SWEA] 1949. [모의 SW 역량테스트] 등산로 조성
SWEA] 1949. (모의 SW 역량테스트) 등산로 조성 SWEA 1949. (모의 SW 역량테스트) 등산로 조성 문제의 저작권은 SWEA에 있습니다 문제의 핵심은 위 규칙 중 3번을 고려하는 것. 처음에는 bfs에 조건을 걸고 산을 깎을 때 dfs로 확인하는 방법을 고려했으나, 결국 dfs 백트래킹으로 하는 것이 확실하고 직관적으로 보여 수정해서 다시 푼 문제. dfs + 백트래킹 방법을 처음부터 적용했더라면, 30분-1시간내에 풀었겠지만, 방황하다가 시간을 조금 더 소요했던 문제였다. 코딩하기 전, 여러 상황을 고려하고 글로 써보고 타이핑을 진행하지만 아직도 많이 부족하다. 그래도 dfs 백트래킹을 적용해서 한번에 성공했을 때는 나름 기뻤던 문제. dfs 백트래킹을 연습하기에 좋은 문제. 1 2 3..
→2019.11.02

• 이전
• 1
• 다음