junyCoding

문제를 요약하면 N,M 크기의 격자판위에 1로 모인곳이 섬이고 모든 섬들을 연결하는 다리길이의 최솟값을 구하는 문제이다 조건 ! 1. 1번과 2 번이 연결되있고 2번과 3번이 연결되어있으면 1번과 3번도 연결되어있는것이다 2. 다리의 길이는 2이상이다. 3. 다리는 섬과 인접하게만 이어질수있다 (백준 문제예시에 그림으로 친절하게 알려준다) 풀이 ! 1. 크루스칼 알고리즘을 사용하면 쉽게 풀수있다. 크루스칼 알고리즘은 최소신장트리 에관한내용인데 아래 동빈나님 블로그에 가면 동영상강의와 함께 친절하게 내용설명을 해주신다. https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https:%2F%2Fwww.googl..

출처 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 궁수에 위치를 선정해주고 선정이 된 이후에 시물레이션을 통해 적을 최대로 처지 할 수 있는 수의 최댓값을 구하는 문제이다. 일단 배열에 세로 열 부분에 궁수를 배치 할 수 있는데 최대 세명까지 배치할 수 있으므로 백트래킹으로 궁수에 위치를 먼저 선점해야 한다. 3명이 된이후에는 원래의 배열을 복사하여 시물레이션을 진행한다. 원래의 배열을 복사하는 이유는 궁수의 배치가 달라질 때마다 시뮬레이션을 진행해야..

출처 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 문제를 읽어보면 파이프를 옮겨 왼쪽 아래 끝부분에 도착하는 경수의 수를 모두 구하는 문제이다. 파이프가 가질수 있는..

이번 문제는 수 사이에 괄호를 적절히 추가하여 식의 결과 값을 최대로 만드는 것이다. 주의해야 할 점은 괄호 안에 괄호를 추가할 수 없다는 것이다 예를 들어 (3 * 2) + (2 + 4 )는 되지만 (3 * 5 - ( 2 + 7 )) 과 같은 경우는 + 연산자가 총 두 쌍의 괄호로 감싸 져 있기 때문에 안된다. 여기서 알 수 있는 점이 있다! 한 연산자가 괄호로 감싸이면 다음 연산자는 절대로 괄호가 씔 수 없다. 어떠한 연산자에 괄호가 씌면 양옆 연산자는 괄호가 씔 수 없다. 예를 들어보자 (문제 조건에서 수식은 괄호를 제외하고는 왼쪽에서 오른쪽으로 진행된다.) 2 * 4 + 4 - 2라는 식이 있을 때 ( 1 ) 현재 식에서 괄호를 씌우고 다음으로 진행하는 경우 (2 * 4) + 4 - 2 => 8 ..