잡담연구소

내 머리 속에 삼성 코테 = bfs + dfs + 빡구현이라서, 오히려 더 어렵게 돌아돌아 풀었다. 70분 정도 걸렸는데, 시험장 가면 떨려서 더 걸릴텐데 벌써 걱정된다. 힝;ㅜ 컴공이 아닌 걸 극복하려고 문제를 무작정 많이 푸는 스타일이지, 엄청 효율적으로 사고하는 편이 아니다. 그래서 구현같은 경우는 주어진 순서를 따라서 차근차근 하나하나씩 함수를 짠다. 내 코드 choice standard 라는 4중 포문으로 기준점 x,y와 길이 d1,d2를 선택한 다음, color_five 함수로 경계선을 -1로 체크해주었다. 그 다음 왼쪽, 오른쪽을 나눠서 divide 함수를 통해서 1,2,3,4 구역별로 정해주었다. 마지막으로 color_inner이라는 bfs문을 돌면서 경계선 혹은 경계선 내부면 5로 체크를..

www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net IDEA 고냥 깜찍한 BFS/DFS문제다. DFS보단 BFS가 편해 BFS로 풀었다. '#'이라는 울타리로 막혀있는 공간 안에서 양과 늑대의 개수를 세어, 더 많은 동물의 개수가 살아남아 최종적으로 아침까지 살아있는 양과 늑대의 수를 구하는 문제다. 1. #이 아니면 BFS문 돌림 2. 큐에서 꺼낸 좌표에 O가 존재하면 양을 , V가 존재하면 늑대의 수를 하나 세준다. 3. 상하좌우에 대해서 마당을..

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net IDEA 여러가지 방법이 있을 수 있겠다. 뭐 유니온파인드를 쓰는 방법도 있겠지만,,,, arr라는 배열에 저장한 후, 배열값을 인덱스로 가지는 그 다음 배열로 넘어가면 될 거 같다. 사이클인지 아닌지 구분하는 방법은 이미 지나온 곳으로 다시 돌아간다면 사이클이다. 1 2 3 4 5 6 7 8 3 2 7 8 1 4 5 6 1부터 시작해서 ..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net IDEA N개의 정점에서 파티가 열리는 특정한 X점까지 갔다가 다시 돌아오는 최소 시간을 물어보는 문제다. 이것도 다익스트라를 이용해서 풀었다. 뭐 플로이드 와샬을 이용해서 풀어도 될 거 같다. 만약, 문제가 양방향이라면 정점 -> 파티장 비용과 파티장 -> 정점의 비용이 같으므로 시작지점을 파티장으로 설정한 후 다익스트라를 이용하면 된다. 하지만, 이 문제는 도로가 단방향이기때문..

www.acmicpc.net/problem/12611261번: 알고스팟첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미www.acmicpc.netIDEA좌측 상단에서 우측 하단 까지 가는데 벽을 최소 몇 개 부숴야 하는 지 묻는 문제다. 여러가지 방법으로 풀 수 있겠지만, 이 또한 다익스트라 로 풀었다. 풀고보니 bfs 같은 느낌도 있다,,,좌측 상단 = 시작 지점 부숴야 하는 벽의 개수 = 비용 으로 바라보면 시작지점부터 어떤 한 정점(우측 하단) 까지의 최소비용을 묻는 문제로 바꿔 생각할 수 있다. 음,,, 다익스트라 예제를 검색하면 ..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net IDEA 버스의 출발도시 , 도착도시 , 버스 비용이 차례대로 주어지고 , 출발점의 도시번호로부터 도착점의 도시번호까지 가는 최소비용을 구하는 문제다. 즉, 한 점에서 다른 한 점까지 가는 최소비용을 구하는 문제이다. 다른 풀이법도 있을 수 있겠지만, 한 점에서 모든 정점까지 가는 최소비용을 구할 수 있는 다익스트라 알고리즘을 이용해서 풀었다. 다익스트라 알고리즘의 대표예제 수..