https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. Logic 기본 3차원 BFS 문제이다. Z축도 있기 때문에 6방향 탐색을 돌아주면 된다. 예외처리만 잘 해주면 무난히 통과하는 문제이다. 2. Code #include using namespace std; int l, r, c; int sx, sy, sz; char building[31][31][31]; bool vis[31][31][31]; int dz[6] = {0, 0, 0, 0, 1, -..
BFS
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 1. Logic 방에 들어갈 때 .이나 $이면 들어갈 수 있기 때문에 방 주변을 이동 가능한 공간으로 둘러싸서 입구를 찾아준다. BFS함수 안에서 각 열쇠마다 키가 없을 때 방문했던 좌표를 queue에 저장해놓고 키를 찾으면 queue에서 뽑았던 좌표를 빼서 확인해준다. 아이디어가 신박했다. 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; i..
https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 1. Logic 입력을 받은 후 물건이 있는 좌표를 받으면 0~5까지의 char타입으로 변경해서 넣어줬다. BFS를 돌면서 입력 받을 때 char타입으로 변경해서 넣어준 물건을 만나면 다시 int타입으로 변경해서 shift연산을 통해 비트계산을 해서 몇번째 물건을 집었는지 기록한다. BFS를 돌면서 E(출구)를 만났을 때 내가 받은 물건과 도착한 시점에서의 물건갯수가 일치하면 걸린시간을 리..
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. Logic 열쇠가 6개밖에 없기때문에 비트로 표현 가능하다. 큐에 현재 열쇠를 모은 상태를 비트로 저장해서 관리해준다. 이 문제에서 나눠질 부분문제를 생각해보면 1. 열쇠를 만날경우 - 현재 열쇠를 모은거와 지금 열쇠를 or연산하여 모은 상태를 구하고 모았던 열쇠면 다시 갈 필요 없기 때문에 건너뛰고 안모은 열쇠면 갱신한 열쇠 컬렉션 상태를 큐에 넣어준다. 2...
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. Logic 정사각형이 같은 섬에 잇는 조건은 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다. 즉 8방향 탐색을 해서 섬의 갯수를 구해주면 된다. 2. Code #include using namespace std; int graph[51][51]; bool vis[51][51]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] ..
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1. Logic 여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다... 1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바..
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. Logic 좌상우하 순서대로 1, 2, 4, 8이라는 값을 가지고 있기 때문에 이는 비트마스킹으로 쉽게 표현할 수 있다. 13을 예시로 들어보면 13을 2진수로 표현하게 되면 1101이다. 즉 13인 방에서 갈수있는 방향을 왼쪽 오른쪽 아래 총 3가지 방향만 갈 수 있다. BFS를 돌 때 dir방향인 dy[4] dx[4]배열을 만들어 놓는데 이와 같은 방향일 때 내가 있는 공간에서 막혀..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. Logic 물에 잠기지 않는 지점이 최대가 될 때를 구하는 문제이다. 처음에 이 문제를 봤을 때 그냥 주변높이 보다 높으면 안전지역인줄 알았는데 문제를 다시 읽어보니 0~최대 높이까지 확인하면서 그중에 가장 많은 안전지역의 갯수를 구하는 문제이다. 풀이 방법은 입력을 받으면서 최대 높이를 구하고 0~최대 높이 까지 BFS를 돌면서 최대 안전 지역의 갯수를 구하면 된다. 2. Code #include..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 1. Logic 다리가 버틸 수 있는 무게가 10억까지이기 때문에 택배의 무게를 이분탐색으로 찾아준다. 이분탐색의 Check함수는 택배의 무게인 mid보다 각 경로가 버틸 수 있는 무게가 크거나 같을 때만 통과시켜 입력받은 출발지에서 시작하여 도착지에 도달할 수 있으면 택배의 무게를 늘리고 도착하지 못하면 택배의 무게를 줄이면서 적절한 택..
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 1. Logic 불의 위치를 담은 queue fire과 지훈이의 위치를 담은 jihun queue 두개를 가지고 풀이했다. 불이 위치한 곳은 애초에 지훈이가 가지 못하고 지훈이가 움직이더라도 불이 오면 안되기 때문에 불을 먼저 BFS를 돌려 움직여줬다. 이후 불이 없는곳에 지훈이를 BFS를 돌려 움직여주면 불이 있는곳을 제외하고 대피할 수 있다. 처음에는 queue 4개를 사용하여..
