본문 바로가기

알고리즘 문제풀이/알고리즘 C++ 풀이

 (71)
[백준] 17141번: 연구소2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17141풀이1.입력으로 주어진 바이러스를 놓을 특정위치 중에 내가 놓을곳 m개를 골라야 한다.나는 입력을 받으면서 따로 pair place[10]배열에 바이러스를 놓을 좌표를 저장해두었다.DFS로 place배열의 인덱스를 가지고 그 중에 m개의 장소를 골랐다. 2.m개의 장소를 고르고 나면 그 부분을 출발점으로 두어야한다.vis[x][y]는 0으로 두고 큐에 넣는다. (vis배열은 -1로 초기화되어있고, 퍼져나가는 시간을 저장해둘것이다.)m개의 장소에 대해 큐에 모두 넣고 BFS를 시작한다. 3.BFS는 아직 방문하지 않았고(vis == -1), 맵이 0이거나 2인 부분을 방문한다. 4.BFS로 vis배열을 모두 채우고, 이중for문으로 v..
[백준] 1963번: 소수경로 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1963풀이BFS+소수 구하기 문제이다.1.네 자리수에 대하여 각 자리수의 숫자를 바꿔가면서 모두 탐색해보면 된다.탐색조건은 1. 아직 방문하지 않은 숫자 2. 소수 3. 1000~9999인 숫자 이다. 2.테스트 케이스 입력받기 전에, 일단 나는 소수를 미리 구해놓았다.소수를 구하는 방법 중에 '에라토스테네스의 체'를 이용하여 1차원 bool형의 배열에 1부터 9999까지 소수면 false, 소수가 아니면 true를 저장해놓았다.'에라토스테네스의 체'의 시간복잡도는 O(Nlog(logN))이다. 배열에 먼저 소수인지 아닌지 체크만 해놓으면 나중에 BFS하면서 방문할때 해당 수가 소수인지 아닌지 바로 배열로 참조가능하므로 상수시간으로 체크할 ..
[백준] 1938번: 통나무 옮기기 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1938풀이하나하나 다~~ 구현하면 되는 문제이다.1. 통나무의 가운데 좌표와 모양 정보만 가지고 진행하면된다. 도착지의 가운데 좌표와 모양정보도!2. vis[x][y][통나무의 모양(ㅡ또는ㅣ)] : 이렇게 vis배열을 3차원으로 두고 BFS로 방문하면 된다.3. 통나무의 모양이 ㅡ인지 ㅣ 인지, 통나무가 있어야할 곳에 1이 있는지(이동할 수 있는 곳인지) 일일이 체크하면서 큐에 넣어야한다. 4. 통나무의 가운데 좌표와 모양이 도착지의 가운데 좌표와 모양과 같다면 BFS를 끝내면된다! 그 때 큐에 가지고 있는 현재 이동한 횟수를 출력해주면된다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/B..
[백준] 9328번: 열쇠 (C++ 풀이) 문제 https://www.acmicpc.net/problem/9328풀이1. 맵을 상하좌우 한칸씩 확장하고 (0, 0)부터 BFS탐색한다.2. 아직 방문하지 않았고 벽이 아니기만 하면 조건에 맞게 탐색한다.3. 문이면, 열쇠가 있는경우 바로 큐에 넣으면 되고, 열쇠가 없으면 door큐에 좌표를 저장해놓는다.door[A] 큐 : (x1, y1), (x2, y2) ... 이런식으로 저장해놓는다. 같은 문자의 문이 여러개 있을수도 있으니까4. 열쇠이면, 해당하는 문을 door큐에서 찾아서 문을 여는 행위를 하면된다. 큐에 넣고, door큐에서는 빼고.5. 빈칸이면 그냥 큐에 넣고6. 문서이면 답을 하나 증가시키고 큐에 넣는다. 이렇게 적어놓고보니까 쉬워보이는데,, 구현할때 한번꼬이고 난 후 좀 헤멨다ㅠㅠ 코..
[백준] 14442번: 벽 부수고 이동하기 2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/14442풀이dist배열을 3차원으로 두고 BFS탐색을 해서 풀었다.1. dist[x좌표][y좌표][벽을몇개부셨는지]2. 벽이 없고 그냥 빈칸이면 dist[nx][ny][wall] = dist[x][y][wall] + 1;3. 벽이 있다면 wall+1이 k이하의 값인지 확인해야한다. 왜냐하면 문제에서 벽은 k번까지 부실 수 있다고 되어있기 때문이다. dist[nx][ny][wall + 1] = dist[x][y][wall] + 1;4. BFS탐색을 마치고 for(i: 0~k)로 0이 아닌 최소값을 구해서 출력한다. 만약에 다 0이면 갈수있는 방법이 없는 것이므로 -1을 출력한다. 코드 https://github.com/ziwonii24/Alg..
[백준] 16234번: 인구 이동 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16234풀이단지번호붙이기 문제와 비슷하다고 생각했다.1. BFS로 그룹으로 묶을 수 있는 것들을 최대한 묶었다.그룹을 묶는 기준은 문제에서 말한 인접한 칸 사이의 차이가 L이상 R이하인 것이다.2. 그러한 같은 그룹을 묶음과 동시에 그 그룹의 인구를 gsum에다가 차곡차곡 더해놓는다. 그리고 그 그룹의 칸의 개수도 세어놓는다.3. int형의 BFS함수로서, 새로운 인구 수를 리턴한다. 탐색하면서 더하고 세어놓았던 gsum/gcnt를 리턴하면 된다.4. BFS를 마치고 만약에 그룹의 칸의 개수가 1이라면 국경선이 열리지 않아 인구이동을 하지 않은 경우이므로, 아무 일도 하지않고 넘어간다. 그러나 칸의 개수가 1이 아니라 2이상이라면, 벡터에 ..
[백준] 9372번: 상근이의 여행 (C++ 풀이) 문제 https://www.acmicpc.net/problem/9372풀이예제를 그래프로 그려보면서 문제를 이해하다보니까 최소 스패닝 트리(MST)를 찾는 문제라는 걸 알았다.문제에서 "주어지는 비행 스케줄은 항상 연결 그래프를 이룬다."라고 되어있다.이 말은 어쨌든 모든 국가를 방문한다는 얘기이므로 정점이 n개인 MST의 간선의 개수인 n-1을 출력하면된다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/9372.cpp결과
[백준] 4179번: 불! (C++ 풀이) 문제 https://www.acmicpc.net/problem/4179풀이BFS로 풀었다.1. 불이 모두 퍼지는데 걸리는 시간을 구하는 BFS를 먼저 구하고지훈이에 대해 탈출하는데 걸리는 시간을 BFS로 구한다.이때, 지훈이는 불이 다녀간 시간보다 먼저 그 곳을 가야한다.2. 불은 하나일수도, 여러개일수도, 없을 수도 있다!3. 마지막에 지훈이가 탈출하는데 걸리는 시간을 저장한 배열을 본다.가장자리부분, 그러니까 행이 0, n-1부분과, 열이 0, m-1부분을 본다.이부분에 지훈이가 다녀간 흔적이 있다면 그중에서 제일 최소인것을 고르면 그게 답이다!없으면 탈출하지 못한 것이다! 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/4179.cpp..

티스토리툴바