devlog

출처 : 18428번: 감시 피하기 (acmicpc.net) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 방법 완전 탐색 + DFS로 풀이할 수 있다. 벽을 세우는 경우를 완전 탐색으로 푸는데 시간을 줄이기 위해 빈 공간을 미리 리스트에 저장해둔다 벽이 3개 생성되면 check 함수를 호출하여 각 선생님의 동서남북 방향을 검사한다 while 문을 통해 board안에서의 동서남북중 한쪽씩 방향을 정해서 검사한다. 만약 검사 중 벽이 나타나면 다른 방향으로 넘어가고 검사중 학생이 나타나면 retu..

출처 : 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 방법 DFS로 완전 탐색으로 풀어야 한다. 연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고 dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다. max_num = -987654321 min_num = 987654321 def dfs(index, sum): glo..

출처 : 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 방법 DFS함수의 인자로 index를 받고 재귀 호출하는 방식으로 문제를 풀이하였다. 만약 index가 삭제할 노드의 인덱스인 경우 삭제할 노드의 부모 노드의 자식이 1명일 경우(삭제당하는 노드 하나) cnt를 +1 해주었다. 그리고 return을 함으로써 삭제할 노드의 자식은 탐색하지 않았다 index가 삭제할 노드의 인덱스가 아닌데 자식이 empty인 경우에도 cnt를 +1 해주었다. 다음 자식이..

출처 : 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 방법 입력받을 때부터 S와 D 지점의 좌표를 기록하고 water의 좌표 벡터에 기록하였다 BFS를 시작할 때 queue에 water의 좌표를 먼저 추가 해준 후 고슴도치의 위치를 que에 넣어 주었는데 이유는 water을 먼저 BFS 하고 그 길을 고슴도치가 갈 수 있냐 없냐 판단을 하기 위해서 이다 (고슴도치를 먼저 이동시키면 동시에 물이 들어오는 경우 복잡해짐) 그런 후 BFS를 돌며 다음 좌표의 board(땅) ..