알고리즘 풀이 (84) 썸네일형 리스트형 [백준] 2667번: 단지번호 붙이기 - JAVA 문제 링크 BOJ 2667번: 단지번호 붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 풀이 과정 모든 지도를 돌며 연결되어 있는 1을 카운트하며 갯수를 세면 되기 때문에 BFS사용하기로 했다. 개인적으로 map을 처리할 때, int형보다 boolean이 처리하기 쉬워서 입력값을 1일 때 true, 0일 때 false로 바꾸어 저장하였다. 이중 반복문을 통해 map배열에 true가 있는지 탐색하고 만약 존재한다면 해당 칸부터 시작해 상하좌우를 탐색하며 queue에 넣으며 방문한 칸을 false로 변경하여 .. [백준] 2630번: 색종이 만들기 - JAVA 문제 링크 BOJ 2630번: 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 과정 문제의 조건이 주어지고 만약 조건이 성립하지 않으면 분할하여 반복하는 구조 ⇒ 분할정복 시작점을 두고 시작점과 주어진 칸들의 값이 일치한다면 카운트, 아니라면 4분할 하는 방법으로 접근하였다 이 문제에서 핵심적인 부분은 divide함수 부분이다. 색종이의 길이를 n, 좌상단 시작점을 (y, x)로 변수명을 정하고 시작하였다. 만약 시작점과 종이의 칸의 숫자가 다르다면 분할을 해야하.. [백준] 2606번: 바이러스 - JAVA 문제 링크 BOJ 2606번: 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 과정 바이러스는 연결된 네트워크를 통해 모두 전파되므로 연결되어 있는 모든 경로를 탐색하면 되는 문제이다. DFS와 BFS 모두 가능하지만, 다른 문제를 풀면서 BFS를 더 많이 사용해서 이번에는 DFS를 사용해 문제를 풀어보기로 했다 dfs(int) 를 통해 방문한 노드를 넘겨주고, 만약 해당 노드를 방문했다면 return, 아니라면 연결된 노드를 다시 dfs로 탐색하였다. 방문한 노드의 visit값을 true로 변경하고.. [백준] 2579번: 계단 오르기 - JAVA 문제 링크 BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 과정 먼저 문제의 핵심은 1번과 2번 규칙이다 계단은 한 번에 한 계단, 두 계단씩만 오를 수 있다 연속된 3개의 계단을 밟으면 안된다 그렇다면, n번째의 계단을 밟는 경우는 몇 가지가 존재할까? n-3을 밟고 n-1번 계단을 밟고 오는 경우와 n-2번을 밟고 오는 경우 2가지가 존재한다. 연속해서 3개의 계단을 밟는 것은 불가능하기 때문에 이외의 경우는 존재하지 않는다. 또한, 조건을 고려하며 한칸을 무조건 뛰는 경우가 발생.. 이전 1 ··· 8 9 10 11 다음
