본문 바로가기

CODING119

[BAEKJOON] 4963번 섬의 개수 이차원 배열에 섬과 바다를 저장하고, 방문하지 않은 섬일 경우 bfs 방식으로 방문할 수 있는 모든 섬들을 방문처리하며 한 번의 호출로 갈 수 있는 섬들을 모두 방문한다. 특히 중요한 점이 대각선 방향으로도 섬과 섬 사이를 이동할 수 있으므로 8가지 방향으로 나아갈 수 있도록 8번의 반복문으로 다음 방문할 섬을 선택하도록 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int cn.. 2022. 3. 22.
[BAEKJOON] 11724번 연결 요소의 개수 위의 예제 입력1과 2를 그림으로 나타내었다. 그래프의 연결요소는 무방향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프를 의미하고, 연결요소의 개수는 아래의 그림과 같이 부분 그래프의 개수를 나타낸다. 먼저 입력받는 노드와 간선을 인접행렬 방식으로 이차원배열에 저장한다. 만약 노드 1번과 2번이 연결되어 있다면 arr [ 1 ] [ 2 ]와 arr [ 2 ] [ 1 ]에 1을, 연결이 안 되어 있다면 0으로 초기화한다. 1번과 2번이 연결되어 있다는 것은 2번과 1번이 연결되어 있다는 것과 같으므로 값을 두 번 저장하는 과정이 필수이다. (전역변수로 선언할 예정이기 때문에 모든 요소가 자동으로 0으로 초기화됨) 전체 노드를 순회하면서 아직 방문하지 .. 2022. 3. 22.
[BAEKJOON] 1697번 숨바꼭질 초기 수빈이가 있는 위치 N 과 동생의 위치 K를 보자. 수빈이가 N-1 또는 N+1 또는 N*2 위치로 이동할 수 있으니 5에서 17로 가는 경우를 그림으로 그려본 것이다. 모든 배열은 0으로 초기화한 후, 해당 위치에 방문한 적이 있으면 넘어가고 그렇지 않다면 큐에 넣어 다음 방문 위치를 저장한다. 큐에서 다음 방문 위치를 꺼내어 해당 인덱스에 지금까지의 움직인 거리에 1을 더하여 저장하는 과정을 반복한다. 다음 방문할 위치가 동생이 있는 곳이라면 즉, 동생이 있는 인덱스 위치가 0이 아니라면 반복을 중단하고 이동한 거리를 반환하여 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead.. 2022. 3. 22.
[BAEKJOON] 2606번 바이러스 이차원배열에 인접된 컴퓨터 번호를 인덱스로 간주하여 연결된 컴퓨터들은 모두 1로 채운다. 이차원배열을 이용할 때 arr[][] 배열이 있을 때 컴퓨터 1번과 2번이 연결된 것을 표현하기 위해서는 아래와 같이 인접행렬 방식으로 행과 열의 인덱스를 바꿔도 연결된 것을 알 수 있도록 한다. 1번과 2번이 연결됐다 == 2번과 1번이 연결됐다 arr[1][2] = 1; arr[2][1] = 1; 인덱스 1(1번 컴퓨터)를 시작으로 연결된 컴퓨터를 찾는다면 해당 컴퓨터와 연결된 또 다른 컴퓨터를 찾기 위해 큐에 저장한다. 큐가 텅 빌 때까지 반복하며 연결된 컴퓨터를 찾아 개수를 센다. 모든 연결된 컴퓨터의 개수를 찾는 것이 아닌, 1번 컴퓨터와의 연결관계만 확인하면 되기 때문에 bfs()를 호출할 때 매개인자로 .. 2022. 3. 14.
[BAEKJOON] 1931번 회의실 배정 이차원 배열에 회의 시작시간과 종료시간을 저장한다. 이전 회의의 종료 시간과 이후 회의의 시작 시간이 서로 겹치지 않으면 된다. 또한, 최대한 많은 회의를 진행하려면 종료시간이 빠른 것을 선택한다. 예제 입력의 회의 시작 시간과 종료 시간 문제의 힌트에서 보이는 바와 같이 총 회의는 4번으로 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. 위의 그래프와 같이 종료시간을 기준으로 정렬하고, 다음 회의는 시작 시간이 같을 경우 회의시간이 짧은 것을 우선으로 선택하면 된다. Comparator 인터페이스를 구현하여 입력되는 값의 종료 시간을 기준으로 오름차순 정렬한다. 즉, 종료시간이 작을 수록 앞쪽에 배치된다. (Comparator 인터페이스 사용법을 아직 모른다면 아래 글 참조해.. 2022. 3. 13.
[BAEKJOON] 1012번 유기농 배추 이중 for문을 돌면서 1인 곳(배추가 있는 곳)을 찾으면 해당 구역의 인근 배추를 모두 탐색하여 방문한다. 구역마다 배추흰지렁이가 하나씩만 존재해야 하기 때문에 배추를 발견한다면 근처 배추에 모두 방문해서 다음번에 재방문을 방지한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N, M, BaeChu, cnt; static int arr[][]; static boolean v.. 2022. 3. 7.

티스토리툴바