기맹기 개발 블로그

BOJ 16946 벽 부수고 이동하기 4 난이도 : 골드 2 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 전략 N, M blankCount[r][c] 2. 1인 칸에 대해서 상하좌우 blankCount를 더한다. 시행착오 4 5 11001 00111 01010 10101 위의 예시를 보자. 1의 과정이 끝난 다음에 blankCount는 다음과 같이 기록될 것이다. 00220 33000 30101 01010 이 때 map..

BOJ 17472 다리 만들기 2 난이도 : 골드 1 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 전략 문제를 보고 처음 생각한 전략은 1. dfs로 섬 구분 2. bfs로 섬 간의 최소 거리를 가지는 간선 만들기 3. 크루스칼로 MST 만들기 그래프 종합 선물세트 같은 느낌이다! 그런데 다리를 이을 때 가로/세로 방향으로 일자로만 가능하며 방향을 중간에 바꿀 수 없다는 제약이 있어서 bfs 안쓰고 간선을 만드는 과정을..