본문 바로가기

완전탐색

 (4)
[백준] 17070번: 파이프 옮기기1 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17070풀이블로그 보면서 풀었다.BFS로 완전탐색하는 방식으로 해결했다.1. (0,0),(0,1)에서 시작해서 파이프 끝이 (n-1, n-1)이면 도착한것!2. 파이프 두칸을 가지고 탐색하지 않고 끝점과 현재 진행방향을 고려했다.3. 큐에 (x, y, 진행방향) 이렇게 세가지 정보가 들어간다.4. 진행방향이 가로 또는 세로면, 그대로 진행하거나 대각선 이동하면 되고   진행방향이 대각선이면, 가로, 세로, 대각선 이동을 해야한다.5. 대각선 이동을 할때에는 (x, y+1)과 (x+1, y)가 0인지도 확인해야한다.6. (x, y)가 (n-1, n-1)이면 ans를 1증가시키고 다음으로 넘어간다. (총 방법의 개수를 세는 것이기 때문)코드 h..
[백준] 14502번: 연구소 (C++ 풀이) 문제https://www.acmicpc.net/problem/14502 풀이다음과 같은 순서로 구현하였다. 1. dfs로 벽 3개가 위치할 수 있는 경우들을 찾았다.2. 벽 3개를 세울 때마다 bfs로 바이러스를 퍼뜨려본다.3. 안전영역의 개수를 센다. 코드https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/14502.cpp 결과
[백준] 15686번: 치킨 배달 (C++ 풀이) 문제https://www.acmicpc.net/problem/15686 풀이도시에 있는 치킨집 중 폐업하지 않을 m개의 치킨집을 골라서 최소의 치킨거리를 찾아내야하는 문제이기 때문에모든 경우의 수를 봐야하므로 완전탐색으로 풀었다. 1. 입력을 받을 때 치킨집(2)이면 모든 치킨집를 저장하는 스택 v에 좌표를 저장해두었다. (vector> v)2. dfs를 통해 치킨집 조합을 만들어낸다. (vector> tmp)3. (tmp.size()==m)이 될때 치킨거리를 계산한다.4. 치킨거리는 tmp에 있는 치킨집을 기준으로 도시를 for문으로 돌면서 집(1)이 나오면 치킨거리를 계산하는 방식이다.5. tmp에 있는 모든 치킨집을 돌았으면 도시의 치킨거리를 계산하여 정답을 담을 ans에 최소값을 갱신한다. ※ 수..
[백준] 14889번: 스타트와 링크 (C++ 풀이) 문제https://www.acmicpc.net/problem/14889 풀이완전탐색 dfs로 풀었다.특이하게도,, dfs안에 dfs가 돌도록 만들었는데바깥 dfs는 스타트팀과 링크팀을 나누는 용도로 만들었다.실제로는 스타트팀만 짜놓고 나머지 선택안된것들이 자동으로 링크팀이라고 하였다.팀이 짜여질때마다 능력치를 계산하는 두번째 dfs가 실행된다.스타트팀이 1 2 3 4 라고 할경우스타트팀의 능력치는 s[1][2] + s[2][1] + s[1][3] + s[3][1] + s[1][4] + s[4][1] + s[2][3] + ... 이런식으로 더해지기 때문이다.이 계산이 모두 끝나고 다음 팀을 짜기 직전에 스타트팀의 능력치와 링크팀의 능력치 차이를 min값으로 갱신해주면 된다. 코드https://github...

티스토리툴바