BFS

[백준 2636] 치즈 C++

2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net BFS 1. 문제 해결 아이디어 치즈의 겉 표면을 찾기 위한 BFS + 겉표면을 녹이는 BFS 이렇게 2개의 BFS를 사용해서 풀었다. BFS를 2개 쓴거라서 아마 내 풀이가 최적의 풀이는 절대 아닐거라 생각한다. 먼저 공기와 맞닿아 있는 치즈표면을 BFS를 통해서 모두 구하면서 개수를 저장해 놓는다. 이때 치즈가 없다면 종료 만약 치즈가 있다면 겉표면 치즈들을 녹이는 BFS를 수행한다. 두 과정을 합칠 수 있을것 같다.. 2. 코드 1 2 3 4 5 6 7 8 9 10..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

[백준 1600] 말이 되고픈 원숭이 C++

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 1. 문제 해결 아이디어 이동할 수 있는 방향이 동서남북 외에도 체스의 말(house)이 움직일 수 있는 8방향이 추가된 문제이다. 처음엔 그냥 8방향만 추가해 주고, 말이 움직이는 방향을 먼저 탐색해 주면 풀리겠지 해서 빠르게 틀렸다. [백준 14442] 벽 부수고 이동하기2 C++ 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 ..

[백준 14442] 벽 부수고 이동하기2 C++

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 1. 문제해결 아이디어 매번 칸을 이동할 때마다 지금까지 몇 개의 벽을 부쉈는지 정보를 가지고 있어야한다. struct P를 만들고 해당 객체를 queue에서 가지고 다니게 하였다. 가장 중요한 visited배열이다. visited[r][c][k] = 1 : r, c를 방문할 때 총 k번 벽을 부수고 방문했음을 의미한다. 만약 다음 좌표가 3, 5이고 지금까지 부순 벽이 2개라면 visited[3][5][3]이 0인지 확..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

[백준 2146] 다리만들기 C++

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 그래프 탐색, BFS 삼성전자 A형 기출문제 1. 문제풀이 아이디어 각 섬을 BFS로 돌면서 해당 섬의 경계좌표를 찾아서 저장한다 섬 간의 거리(경계좌표간의 거리)를 모두 찾아보면서 최솟값을 구한다 2. 코드 설명 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51..

[백준 10026] 적록색약 C++

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net BFS 연습 #1 전형적인 BFS 탐색 문제이다 색약인 경우에 'R' 과 'G' 를 같다 생각하고 탐색하게 해주면 문제없이 풀 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 6..