https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 4방향이 아닌, 2방향 bfs 문제이다. 우선 dx배열에 up과 down을 저장해주자. (down저장할 때 꼭 마이너스 붙이자ㅜㅜ 그것때문에 조금 당황했다..) 만약 현재 위치와 목표 층수가 같다면 0을 출력하고 종료한다. 그렇지 않다면 bfs 탐색을 시작하자! 현재 위치에서 위로 올라가는 경우와, 내려가는 경우에 대해 모두 탐색해주자. 그 경우들이 0층 이상 ~ F층 이하이고, 아직 방문하지 않았다면 큐..
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자열 T에 대해 T가 empty되지 않을 때 까지 맨 뒤부터 탐색을 진행한다. A를 만났다면 그냥 A를 지워주고, B를 만났다면 문자열을 뒤집은 뒤 맨 앞을 지워준다. (B를 추가할 때 문자열을 뒤집고 나서 맨 뒤에 B를 추가하기 때문에, 원래 상태로 돌아가려면 문자열을 뒤집고 그 문자열의 맨 앞을 지워야 한다!) 만약 이 과정에서 T가 S와 같아진다..
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 이 문제는 bfs 탐색을 할 때 마다 입력값을 바꿔주게 되면 다음 탐색에 영향이 가므로, 약간의 테크닉이 필요하다. 그것이 바로 string과 set의 사용이다! 우선, 문제의 입력값을 string으로 받는다. 그리고 나서 string의 인덱스 값을 이용하여 행렬 좌표로 변환을 진행한다. 변환된 좌표값으로 상하좌우 주변을 탐색하고, 올바른 범위일 때 좌표값을 다시 string의 인덱스 값으로 변환하여 swap함수를 적용시킨다! 여타 bfs와 마찬가지로 방문 여부를 체..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net bfs문제다. 근데 주의할 점은 물 -> 고슴도치 -> 물 -> 고슴도치 순으로 bfs를 진행해줘야 한다는 것! 먼저 물을 담고 있는 큐의 사이즈만큼 탐색을 진행한다. 그리고 고슴도치 위치를 담고 있는 큐의 사이즈만큼 탐색을 진행해주면 된다. 생각보다 간단한데, 이런 유형의 문제를 처음 푸는 분들은 조금 당황할 수도 있다. 왜냐?? 바로 큐의 사이즈만큼 탐색을 하기 때문이다. bfs문제에서 큐의 사이즈만큼..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수를 2개씩 묶거나, 더해가면서 수열의 합 중 최대 값을 찾는 문제이다. 양수를 담을 벡터 하나, 0을 담을 벡터 하나, 음수를 담을 벡터 하나 총 3개의 벡터를 활용하였다. 양수는 내림차순으로, 음수는 오름차순으로 정렬해준 뒤, 최댓값을 계산하면 된다! 먼저 양수에서는, 나의 다음 숫자가 1인 경우가 중요하다. 양수는 거의 곱하는 것이 이득인데, 1일 때는 곱하는 것보다 더하는 것이 더 이득이..
https://www.acmicpc.net/problem/14442 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 이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다. 아래 코드를 보자 if (nx = n || ny = m) continue; // 이미 방문한 경우 if (visited[nx][ny][wall]) continue; if (board[nx][ny] == 0) { q.push({nx,ny,ans..
