C++ (64) 썸네일형 리스트형 [백준] 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.. [백준] 9205번: 맥주 마시면서 걸어가기 (C++ 풀이) 문제 https://www.acmicpc.net/problem/9205풀이점과 점사이의 맨해튼 거리를 계산하고그 거리가 20병*50m=1000m 이내이면 그래프로 저장한다.dfs로 시작점인 0부터 탐색을 하는데첫번째 예제에서는 모든 좌표가 1000이내에 있어서 그래프가 하나로 연결되어있다.그래서 시작점에서 도착점까지 무사히 갈 수 있는데두번째 예제에서는 중간에 1000이내에 갈 수 없는 지점이 있다.그래서 그래프가 2개가 되는데 시작점에서부터 dfs탐색을 할 경우 도착점까지 탐색을 하지 못하게 된다.dfs탐색을 마친후 도착점에 방문했는지 여부에 따라 happy or sad를 출력하면 된다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/9.. [백준] 17135번: 캐슬 디펜스 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17135풀이궁수배치를 어떻게 하느냐에 따라 죽일 수 있는 적의 수가 다르다. 최대한 많은 수의 적을 죽일때 그 수를 출력하는 문제이다.1. 나는 dfs로 궁수를 배치했다. 최대 15C3의 조합으로 궁수를 배치할 수 있다.2. 3명의 궁수를 배치하고 나면 각 궁수에 대하여 죽일 수 있는 적을 표시하는 작업을 한다.나는 이 작업을 bfs로 탐색했다.3. bfs로 해당 궁수에 대하여 사정거리까지 퍼져나가면서 가장 가깝고 제일 왼쪽에 있는 적을 찾는다.bool형 2차원배열에 찾은 적을 true로 표시한다. 궁수 3명이 한명의 적을 선택해도 상관없다. 각각이 찾으면 true로 표시할 뿐이다. 궁수 3명을 다 돌고 나면 true로 표시한 적을 1에서 .. [백준] 9376번: 탈옥 (C++ 풀이) 문제 https://www.acmicpc.net/problem/9376 풀이두 죄수를 탈옥시키기 위해 열어야하는 문의 최소값을 구하는 문제이다.탈옥하는데 최단시간이나 최단거리를 구하는게 아니라 돌아가더라도 문을 최대한 적게 열고 가는게 더 중요한 문제다.탈옥시켜야 하는 죄수가 두명이나 되고 열었던 문을 또 열게할수는 없으니 문을 공유해야 하는게 어려웠다. 문제를 푸는 방법은 다음과 같다.1. 외부사람 상근이가 문을 열고 들어가는 방법2. 죄수1이 문을 열고 나가는 방법3. 죄수2가 문을 열고 나가는 방법이 세가지 방법을 더한 후 그 중에 가장 작은 값이 이 문제의 정답이다.근데 문이 있는 지점은 세사람이 모두 열고 지나갔으므로 -2를 하여 한번만 여는것으로 해두어야한다. 상근이가 밖에서 안으로 들어와야하.. [백준] 2638번: 치즈 (C++ 풀이) 문제 https://www.acmicpc.net/problem/2638풀이1. 문제에서 가장자리 칸은 치즈를 두지 않는다고 했으니, (0,0)에서 BFS를 시작해서 상하좌우에 치즈칸이 있으면 그 치즈칸의 vis배열값을 +1해준다.-> (0,0)에서 시작하는 이유는 치즈의 외부와 내부를 구분하기 위함이다. 그래서 치즈의 가장자리만 탐색하기 위함이다. 2. arr배열값이 1이고(치즈칸) vis배열값이 2이상인 것들만 arr배열값을 0으로 바꾼다. -> 치즈 녹이기 작업 3. vis배열을 0으로 초기화하고 arr배열에 1이 다 사라질때까지 반복한다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2638.cpp결과처음에 치즈의 내부와 외부를 구.. [백준] 1261번: 알고스팟 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1261풀이처음에는 벽부수고 이동하기 처럼 3차원배열 놓고 풀었다가 메모리초과가 났다.이 문제는 최단거리로 가려는게 목적이 아니라, 돌아가더라도 벽을 최소한 적게 부시고 가는 게 목적인 문제이다.그래서 방문한 지점에 대해서도 다시한번 그 지점이 벽을 부신 횟수가 최소인가?를 다시 체크하고 다시 방문하기도 한다. 나는 방문한 지점을 다시 방문하지 않아 계속 틀렸다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1261.cpp결과 [백준] 1389번: 케빈 베이컨의 6단계 법칙 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1389풀이BFS로 풀었다.1번사람에 대해서 다른 연결된 친구들까지의 단계거리(?)를 모두 계산해서 1차원의 dist배열에 저장한다.dist배열은 -1로 초기화되어있고, 1에서 1로 가는 거리는 0이다.1번사람에 대해 BFS로 모두 탐색해서 dist배열을 다 채웠으면dist배열 값을 모두 더해서 제일 작은 값에 대해서만 ans에 따로 저장해둔다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1389.cpp결과 [백준] 1525번: 퍼즐 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1525풀이1. 단순히 생각하면 퍼즐 단계 단계 BFS로 탐색하면 되지만, 3X3배열을 저장해놓아야 한다는 메모리적인 부담이 있다.이 문제는 메모리제한이 32MB이기 때문에 배열을 저장하는 것은 옳지 않다.그래서 생각해낸것이 string으로 저장하는 것이다.결국에는 이 문자열이 "123456780"이 되면 펴즐이 완성이 되는 것이다. 2. 큐에 현재문자열과 걸린 시간을 저장한다. 현재 문자열에 대해서 이제 처리를 하면되는데,관건은 0의 위치다. 0의 상하좌우에 있는 숫자들은 0으로 이동할 수 있기 때문이다.string에 있는 find함수로 '0'을 찾고, 상하좌우를 탐색해주기 위해서 3X3배열일때 0의 (x, y)좌표를 계산을 통해 찾는다.x.. 이전 1 2 3 4 ··· 8 다음
