본문 바로가기

분류 전체보기

 (70)
[백준] 17406번: 배열 돌리기 4 문제 https://www.acmicpc.net/problem/17406 풀이 이 문제를 풀어나간 순서를 간단히 말하자면 다음과 같다. 1. 연산 순서 정하기 2. 회전 연산하기 3. 배열값 구하기 1. 연산 순서 정하기 회전 연산이 여러개면, 연산을 수행한 순서에 따라 배열이 달라지기 때문에 연산 순서 조합을 모두 구해야한다. 연산은 최대 6개이기때문에 배열을 미리 만들어놔서 입력받을때 배열에 차례로 저장해두었다. 배열에 연산을 미리 저장해둔 이유는 배열의 인덱스를 이용하여 연산 순서 조합을 구하기 위함이다! 연산순서는 dfs(백트래킹) 방법으로 구했다. 2. 회전 연산하기 제일 많은 시간이 걸렸던 부분.. [SWEA] 1954번: 달팽이 숫자 문제를 연습한다면 좋을 것 같다.. 일단, 1번에서 정한 ..
[백준] 2468번: 안전 영역 문제 https://www.acmicpc.net/problem/2468 풀이 1. input을 받으면서 HashSet에 지역의 높이정보를 저장했다. HashSet을 이용한 이유는, 중복저장을 하지 않기 위함과 해당 높이를 활용하여 물높이를 높일 것이기 때문이다. 이게 무슨소리냐면, 예를들어, 예제 입력1 같은 경우에는 높이 정보가 골고루 되어있어서 2부터 9까지 반복문으로 물의 높이를 올려가면서 안전영역을 계산할 수 있겠지만 만약에, 4 1 1 1 1 100 100 100 100 1 1 1 1 100 100 100 100 이런 경우면은 1부터 100까지 물의 높이를 1씩 증가하는 것은 비효율적이라고 생각해서 Set에 높이정보를 따로 저장한 것이다. 추가로, HashSet은 HashMap기반으로 만들어져 ..
[백준] 17141번: 연구소2 문제 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배열을 모두 채우고, ..
[백준] 1963번: 소수경로 문제 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번: 통나무 옮기기 문제 https://www.acmicpc.net/problem/1938 풀이 하나하나 다~~ 구현하면 되는 문제이다. 1. 통나무의 가운데 좌표와 모양 정보만 가지고 진행하면된다. 도착지의 가운데 좌표와 모양정보도! 2. vis[x][y][통나무의 모양(ㅡ또는ㅣ)] : 이렇게 vis배열을 3차원으로 두고 BFS로 방문하면 된다. 3. 통나무의 모양이 ㅡ인지 ㅣ 인지, 통나무가 있어야할 곳에 1이 있는지(이동할 수 있는 곳인지) 일일이 체크하면서 큐에 넣어야한다. 4. 통나무의 가운데 좌표와 모양이 도착지의 가운데 좌표와 모양과 같다면 BFS를 끝내면된다! 그 때 큐에 가지고 있는 현재 이동한 횟수를 출력해주면된다. 코드 https://github.com/ziwonii24/Algorithm/blob/mas..
[백준] 9328번: 열쇠 문제 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 문제 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/ziwonii..
[백준] 16234번: 인구 이동 문제 https://www.acmicpc.net/problem/16234 풀이 단지번호붙이기 문제와 비슷하다고 생각했다. 1. BFS로 그룹으로 묶을 수 있는 것들을 최대한 묶었다. 그룹을 묶는 기준은 문제에서 말한 인접한 칸 사이의 차이가 L이상 R이하인 것이다. 2. 그러한 같은 그룹을 묶음과 동시에 그 그룹의 인구를 gsum에다가 차곡차곡 더해놓는다. 그리고 그 그룹의 칸의 개수도 세어놓는다. 3. int형의 BFS함수로서, 새로운 인구 수를 리턴한다. 탐색하면서 더하고 세어놓았던 gsum/gcnt를 리턴하면 된다. 4. BFS를 마치고 만약에 그룹의 칸의 개수가 1이라면 국경선이 열리지 않아 인구이동을 하지 않은 경우이므로, 아무 일도 하지않고 넘어간다. 그러나 칸의 개수가 1이 아니라 2이상이라..

티스토리툴바