백준 15686 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 전 나의 생각 이 문제를 처음 봤을 땐 BFS로 풀면 될 것이라고 생각했지만 생각을 정리하다 보니 결코 BFS로 풀면 안되는 문제였다. 만약 BFS로 진행하게 된다면 시간초과가 난다. 이유는 당연하게도 너무 많은 탐색을 진행하게 되기 때문이다. 또한 거리를 탐색할 수 있는 효율적인 계산식이 있는데 하나 씩 탐색하는 것은 굉장히 비효율 적이다. 그렇기 때문..
알고리즘 및 자료구조/백트래킹
백준 1941 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 전 나의 생각 우선 처음부터 BFS로 풀겠다고 접근하면 안된다. 왜냐하면 BFS는 자유로운 방향으로 'ㅜ' 나 'ㅏ' 의 방향처럼 퍼질 수는 있지만 역으로 다시 돌아와서 재탐색 하지 않는다. 그래서 모든 분기를 돌며 탐색을 진행하는 DFS와 같이 사용하면 쉽게 풀 수 있다. DFS는 학생들의 모든 조합을 찾기 위해 사용한다. 이유는 모든 조합을 구하면 모든 경우의 수를 구할 수 있..
백준 16987 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 전 나의 생각 백트래킹을 사용하여 풀 수 있는 문제지만 조건을 잘 걸어놔야만 정확한 결과를 얻을 수 있다. 우선 재귀함수가 어떤 방식으로 진행되야 할지 미리 파악해야 한다. 1. 계란의 내구도가 존재하여 다른 계란을 깰 수 있는 경우 2. 계란이 깨져서 더 이상 다른 계란을 깰 수 없는 경우 3. 계란의 내구도가 존재하지만 다른 계란이 다 깨져 있는 경우 이렇게..
