그래프의 정점과 간선 중 일부를 선택해서 구성하는 트리를 신장 트리라고 한다. 가중치 그래프일 때, 가장 적은 비용으로 모든 정점들을 연결하는 것이다. 최소 신장 트리는 순환하는 사이클 구조를 절대 가져서는 안 된다.
노드의 개수가 n개일 때
코드로 구현하면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Kruskal {
int[] parent;
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// Node, Edge Tokenizer
StringTokenizer neTokenizer = new StringTokenizer(reader.readLine());
int nodeCount = Integer.parseInt(neTokenizer.nextToken());
int edgeCount = Integer.parseInt(neTokenizer.nextToken());
// Kruskal Algorithm은 서로소 집합의 개념을 이용해 서로 다른 두 정점을
// 연결했을 때 사이클이 발생하는지 검사한다
// 배열로 표현한 트리를 만들자
parent = new int[nodeCount];
// 각각의 원소들이 자신을 대표자로 하는 집합으로 만들어 줌
for (int i = 0; i < nodeCount; i++) {
parent[i] = i;
}
// 간선 정보 해독
int[][] edges = new int[edgeCount][3];
for (int i = 0; i < edgeCount; i++) {
StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
edges[i][0] = Integer.parseInt(edgeTokenizer.nextToken());
edges[i][1] = Integer.parseInt(edgeTokenizer.nextToken());
edges[i][2] = Integer.parseInt(edgeTokenizer.nextToken());
}
// 1. 간선들을 가중치 기준으로 정렬
Arrays.sort(edges, Comparator.comparingInt(edge -> edge[2]));
// 2. 간선들을 가중치 순서대로 순회하면서 고른다
int picked = 0; // 선택한 간선 수
int totalWeight = 0;
List<String> pickedEdges = new ArrayList<>();
for (int i = 0; i < edgeCount; i++) { // 최대로 많이 순회해 봤자 간선의 수만큼
int start = edges[i][0];
int end = edges[i][1];
// * 사이클이 존재하는지 확인
if(findSet(start) != findSet(end)) {
// 두 원소를 하나의 집합으로
union(start, end);
// 간선을 골랐음을 표시
picked++;
totalWeight += edges[i][2];
pickedEdges.add(Arrays.toString(edges[i]));
}
// 3. 고른 간선의 개수가 n-1 개가 될 때까지
if (picked == nodeCount - 1) break;
}
System.out.println("totalWeight = " + totalWeight);
System.out.println("pickedEdges = " + pickedEdges);
}
// union: x, y가 주어졌을 때 둘을 합하는 연산
public void union(int start, int end) {
parent[findSet(end)] = findSet(start);
}
// findSet: 내 부모가 나일 때까지 재귀 호출
public int findSet(int node) {
if (parent[node] != node)
return findSet(parent[node]);
else return node;
}
public static void main(String[] args) throws IOException {
new Kruskal().solution();
}
}
하나의 정점에서 시작해서 정점을 하나씩 추가하는 알고리즘이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Prim {
public int solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer neTokenizer = new StringTokenizer(reader.readLine());
int nodeCount = Integer.parseInt(neTokenizer.nextToken());
int edgeCount = Integer.parseInt(neTokenizer.nextToken());
// 가중치가 저장된 인접 행렬 사용
int[][] adjMatrix = new int[nodeCount][nodeCount];
for(int i = 0; i < edgeCount; i++) {
StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
int start = Integer.parseInt(edgeTokenizer.nextToken());
int end = Integer.parseInt(edgeTokenizer.nextToken());
int weight = Integer.parseInt(edgeTokenizer.nextToken());
// 정보를 인접행렬에 어떻게 저장할까요?
adjMatrix[start][end] = weight;
adjMatrix[end][start] = weight;
}
// 방문정보 (선택정보)
boolean[] visited = new boolean[nodeCount];
// 현재 선택된 정점들에서 해당 정점까지 도달 가능한 가장 짧은 거리
int[] dist = new int[nodeCount];
Arrays.fill(dist, Integer.MAX_VALUE);
// 어느 노드에서 도달했는지 정보를 저장
int[] parent = new int[nodeCount];
// 1. 임의의 정점 선택
dist[0] = 0;
parent[0] = -1;
// 모든 정점을 선택할때까지 순회한다.
for (int i = 0; i < nodeCount; i++) {
int minDist = Integer.MAX_VALUE;
int idx = -1;
// 2-1. 인접한 정점 중 최소 비용 간선으로 연결되는 정점을 찾는다.
for (int j = 0; j < nodeCount; j++) {
if (!visited[j] && dist[j] < minDist) {
// 선택 후보
minDist = dist[j];
idx = j;
}
}
// 가장 가까운곳 방문
visited[idx] = true;
// 2-2. 정점 정보를 바탕으로 도달 가능 정보를 갱신한다.
// idx로 부터 다른 정점들에 도달할 수 있는지를 확인하고 (adjMatrix)
// 그 정보를 바탕으로 dist 배열을 업데이트
for (int j = 0; j < nodeCount; j++) {
// 1. 방문하지 않았고,
// 2. 연결되어 있으며,
// 3. 본래 최단 거리보다 더 짧게 도달 가능할 때
if (
!visited[j] &&
adjMatrix[idx][j] != 0 &&
dist[j] > adjMatrix[idx][j]
) {
// dist, parent 갱신
dist[j] = adjMatrix[idx][j];
parent[j] = idx;
}
}
}
// Prim 알고리즘의 총 가중치는 dist 배열에 저장됨
int totalWeight = 0;
for (int i = 0; i < nodeCount; i++) {
totalWeight += dist[i];
}
System.out.println(totalWeight);
// 어떤 순서로 연결되었는지는 parent에 담김
System.out.println(Arrays.toString(parent));
return totalWeight;
}
public static void main(String[] args) throws IOException {
new Prim().solution();
}
}
문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
n-1
인 정수로 표현합니다.입출력 예
n | computers | return |
---|---|---|
3 | [[1, 1, 0], [1, 1, 0], [0, 0, 1]] | 2 |
3 | [[1, 1, 0], [1, 1, 1], [0, 1, 1]] | 1 |
import java.util.LinkedList;
import java.util.Queue;
//https://school.programmers.co.kr/learn/courses/30/lessons/43162
public class Programmers43162 {
public int solution(int n, int[][] computers) {
int answer = 0;
// 방문했는지 파악
boolean[] visited = new boolean[n];
// 모든 컴퓨터(정점) 순회
for (int i = 0; i < n; i++) {
// 이 컴퓨터가 속한 네트워크를 확인한 적 없다면
// 이 컴퓨터를 방문한 적 없다고 나올 것
if (!visited[i]) {
// BFS or DFS
network(i, n, computers, visited);
// 네트워크 하나 완성
answer++;
}
}
return answer;
}
public void network(
// 몇 번 컴퓨터부터 확인 예정인지
int computer,
// 컴퓨터의 개수
int n,
// 컴퓨터 연결 정보
int[][] computers,
// 컴퓨터 방문 정보
boolean[] visited
) {
Queue<Integer> toVisit = new LinkedList<>();
toVisit.offer(computer);
while(!toVisit.isEmpty()) {
int next = toVisit.poll();
for (int i = 0; i < n; i++) {
// 연결되어 있고 아직 방문한 적 없다면
if(computers[next][i] == 1 && !visited[i]) {
toVisit.offer(i);
visited[i] = true;
}
}
}
}
public static void main(String[] args) {
int answer = new Programmers43162().solution(3, new int[][] {
{1, 1, 0},
{1, 1, 1},
{0, 1, 1}
});
System.out.println("answer = " + answer);
}
}
문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
입출력 예
begin | target | words | return |
---|---|---|---|
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 4 |
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Programmers43163 {
public int solution(String begin, String target, String[] words) {
int answer = 0;
// words 내에 타겟이 존재하지 않으면 바로 문제 종료
if (!Arrays.asList(words).contains(target)) return answer;
// 문제에는 단어를 다시 활용하면 안 된다는 조건이 없지만
// 최단 거리를 구하기 때문에 방문한 곳은 탐색하지 않음
// 단어가 없을 경우 탐색을 끝내고 무한 루프에 빠지지 않게 하기 위해
boolean[] visited = new boolean[words.length];
// 거리를 저장하기 위한 distance 배열
// begin에서 words[i]까지 도달하는 데 걸린 최소 변환 횟수
// 원래는 Queue<int[]> 형식으로 주던 것을 Queue<integer>로, 두 번째 값은 외부 배열로
int[] distance = new int[words.length];
// begin에서 일단 도달할 수 있는 단어를 Queue에 넣기
Queue<Integer> toVisit = new LinkedList<>();
for (int i = 0; i < words.length; i++) {
// 시작 단어와 유사 단어일 경우
if (similar(begin, words[i])){
// 큐에 넣기
toVisit.offer(i);
// 거리 정보 업데이트
distance[i] = 1;
visited[i] = true;
}
}
// BFS 진행
while (!toVisit.isEmpty()) {
int nextIdx = toVisit.poll();
String nextWord = words[nextIdx];
// 이번 단어가 타겟이라면
if(nextWord.equals(target)) {
answer = distance[nextIdx];
break;
}
// 다음 방문 대상 선정
for (int i = 0; i < words.length; i++) {
// 유사하고 방문하지 않았다면
if(similar(nextWord, words[i]) && !visited[i]) {
toVisit.offer(i);
visited[i] = true;
distance[i] = distance[nextIdx] + 1;
}
}
}
return answer;
}
// 인접 판단 메소드
// 두 단어가 한 글자 제외 동일한지
private boolean similar(String word, String target) {
int same = 0;
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) == target.charAt(i)) same++;
}
return (same + 1 == word.length());
}
public static void main(String[] args) {
System.out.println(
new Programmers43163().solution("hit", "cog", new String[]{
"hot", "dot", "dog", "lot", "log", "cog"
})
);
System.out.println(
new Programmers43163().solution("hit", "cog", new String[]{
"hot", "dot", "dog", "lot", "log"
})
);
}
}
Postman을 이용한 테스트도 해당이 되지만 실제로 우리가 만든 어플리케이션은 Controller, Service, Repository 등등 다양한 부분으로 나누어져 있다. 이 작은 단위의 테스트는 어떻게 진행할 수 있는지 고민해 봐야 한다. Test 코드는 무조건 필요하지는 않다. 없어도 잘 작성하기만 한 프로그램이라면 잘 돌아간다. 다양한 상황을 만들어 보기 위해 계속 Request를 만드는 등 편리함에서도 뒤떨어진다.
테스트 코드도 장단점을 가진다.
장점 | 단점 |
---|---|
잘못된 방향의 개발 예방 | 코드 작성으로 인한 개발 시간 증가 |
전체적인 코드의 품질 향상 | 테스트 코드 유지 보수 비용 |
오류 상황에 대한 대처 향상으로 개발 시간 단축 | 테스트 작성법 학습 필요 |
Spring에는 기본으로 테스트용 도구가 포함되어 있다.
testImplementation 'org.springframework.boot:spring-boot-starter-test'
H2 데이터베이스
H2는 초기 단계의 개발 및 테스트를 하는 과정에서 많이 활용되는 관계형 데이터베이스이다. 일반적으로 단위 테스트, 통합 테스트를 진행할 때 많이 활용한다.
spring:
datasource:
url: jdbc:h2:mem:testdb
driver-class-name: org.h2.Driver
username: sa
password: password
jpa:
database: h2
database-platform: org.hibernate.dialect.H2Dialect
Repository가 가지고 있는 기능이 제대로 동작하는지 코드를 작성하는 것이다.
@DataJpaTest
는 Spring Boot에서 JPA의 단위 테스트를 위해서 제공하는 기능이다. 단위 테스트는 보통 메소드 단위의 코드를 테스트하는 경우가 많은데, Repository 코드를 테스트 하고자 한다면 나머지 Service나 Controller, 또는 Spring의 Dispatcher Servlet 등 다양한 부분들은 필요가 없는 경우가 많다. 그래서 다른 불필요한 부분들을 제거하고 JPA를 테스트 하기 위한 부분들만 사용하도록 해 주는 어노테이션이라고 볼 수 있다. 이와 @Autowired
어노테이션을 함께 활용해서 UserRepository
를 주입받을 수 있다. (@Autowired
의 경우 테스트 코드가 아니어도 활용할 수 있다.)
이를 테스트 코드로 작성하면 아래처럼 작성할 수 있다.
@Test
public void testSaveNew() {
// given
String username = "jeeho.dev";
UserEntity user = new UserEntity();
user.setUsername(username);
// when
user = userRepository.save(user);
// then
assertNotNull(user.getId());
assertEquals(username, user.getUsername());
}
여기서 assert
라는 표현이 붙은 메소드가 두개 등장한다. Assertion은 일반적인 테스트 과정에서, 기대한 대로 결과가 드러났는지를 확인하기 위한 코드를 의미합니다.
assertNotNull
: 주어진 값이 null
이 아닌지를 검증한다.assertEquals
: 주어진 두 값이 동일한지를 검증한다.이후 실행을 해 보면 테스트가 통과된 것을 알 수 있다.
여기서 제시되는 테스트 이름은, @DisplayName
어노테이션을 통해 정할 수 있다.
이번에는 중복된 이름이 들어가지 못하는 테스트 코드를 작성해 보자.
@Test
@DisplayName("새 UserEntity를 데이터베이스에 추가 실패")
public void testSaveNewFail() {
// given username을 가지고 UserEntity를 먼저 save
String username = "huisu";
UserEntity userGiven = new UserEntity();
userGiven.setUsername(username);
userRepository.save(userGiven);
// when 같은 username을 가진 UserEntity save 시도
UserEntity user = new UserEntity();
user.setUsername(username);
// when-then 예외 발생
assertThrows(Exception.class, () -> userRepository.save(user));
}
이번에는 이름으로 검색하는 Repository 테스트 코드를 작성해 보자.
@Test
@DisplayName("username으로 UserEntity 찾기")
public void testFindByUsername() {
// given: 검색할 유저
UserEntity userGiven = new UserEntity();
String username = "huisu";
userGiven.setUsername(username);
userRepository.save(userGiven);
// when: UserRepository에 findByUsername
Optional<UserEntity> user = userRepository.findByUsername(username);
// then: Optional.isPresent(), username == username
assertTrue(user.isPresent());
assertTrue(user.get().getUsername() == username);
}
이번엔 Service
코드를 단위 테스트 해 보자. 이때 고려해야 할 부분은, UserService
의 경우 UserRepository
가 있어야 정상적으로 작동한다는 점이다.
@Slf4j
@Service
@RequiredArgsConstructor
public class UserService {
private final UserRepository repository;
// ...
단위 테스트는 하나의 클래스를 격리해서 테스트 하는 것을 목표로 하는 만큼, 다른 단위에서 테스트 해야되는 repository
의 기능에 의존해서는 안 된다. 이런 상황에서 저희는 단위 테스트를 하기 위해서 UserRepository
의 역할을 따라 하는 임시 객체를 만들어서 사용한다. 이런 객체를 Mock
(모조)이라고 부른다. 이 Mock
객체를 사용하기 위해 다음과 같이 테스트 코드를 준비한다.
@ExtendWith(MockitoExtension.class)
public class UserServiceTests {
@Mock
private UserRepository userRepository;
@InjectMocks
private UserService userService;
// ...
@ExtendWith
는 저희가 Mock
객체를 만들기 위해서 Mockito
를 사용한다는 부분을 첨부한 어노테이션이다. 이 어노테이션이 있으면 저희는 @Mock
과 @InjectMocks
를 사용할 수 있다.
이제 User 객체를 추가하는 테스트 코드를 작성해 보자.
import com.example.contents.dto.UserDto;
import com.example.contents.entity.UserEntity;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.extension.ExtendWith;
import org.mockito.InjectMocks;
import org.mockito.Mock;
import org.mockito.junit.jupiter.MockitoExtension;
import static org.mockito.Mockito.when;
import static org.junit.jupiter.api.Assertions.*;
@ExtendWith(MockitoExtension.class)
// Mocking 가짜 객체를 만들어 주는 클래스
public class UserServiceTests {
// Mock: 인터페이스로 메소드를 가지고 있지만 내부 동작은 정의되어 있지 않은 모조 객체
@Mock
private UserRepository userRepository;
// IngectMocks:
@InjectMocks
private UserService userService;
// UserDto를 입력받아 UserDto(id != null)를 반환
@Test
@DisplayName("UserDto로 createUser")
public void testCreateUser() {
// given:
// 1. UserRepository가 전달받을 UserEntity 정의
String username = "huisu";
UserEntity userEntityIn = new UserEntity();
userEntityIn.setUsername(username);
// 2. UserRepository가 반환할 UserEntity 정의
Long userId = 1L;
UserEntity userEntityOut = new UserEntity();
userEntityOut.setId(userId);
userEntityOut.setUsername(username);
// 3. UserRepository.save()의 기능을 따라 하도록 설정
// userRepository는 아래와 같이 기능할 것이다라고 가정
when(userRepository.save(userEntityIn))
.thenReturn(userEntityOut);
when(userRepository.existsByUsername(username))
.thenReturn(false);
// when:
UserDto userDto = new UserDto();
userDto.setUsername(username);
UserDto result = userService.createUser(userDto);
// then:
assertEquals(userId, result.getId());
assertEquals(username, result.getUsername());
}
}
이제 Controller
로 넘어가 보자. Controller
같은 경우 단위 테스트를 위해, 데이터가 HTTP 요청으로 들어오는 것을 가정해야 한다. 이때 사용할 수 있는 객체가 MockMvc
입니다. MockMvc
를 사용하면 HTTP 요청을 보낸 상황을 가정하고, 돌아온 응답에 대해 assertion을 진행할 수 있는 방법을 제공한다.
이때 MockMVC는 직렬화와 역직렬화를 지원하지 않아서 수동으로 해 주는 클래스가 필요하다.
package com.example.contents;
import com.fasterxml.jackson.annotation.JsonInclude;
import com.fasterxml.jackson.databind.ObjectMapper;
import java.io.IOException;
public class JsonUtil {
static byte[] toJson(Object object) throws IOException {
ObjectMapper mapper = new ObjectMapper();
mapper.setSerializationInclusion(JsonInclude.Include.NON_NULL);
return mapper.writeValueAsBytes(object);
}
}
이후 POST “/users” 요청을 받았을 때를 테스트해 보자.
import com.example.contents.dto.UserDto;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.extension.ExtendWith;
import org.mockito.InjectMocks;
import org.mockito.Mock;
import org.mockito.junit.jupiter.MockitoExtension;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.CoreMatchers.notNullValue;
import static org.junit.jupiter.api.Assertions.*;
import static org.mockito.Mockito.when;
import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.post;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.*;
import org.springframework.http.MediaType;
import org.springframework.test.web.servlet.MockMvc;
import org.springframework.test.web.servlet.ResultActions;
import org.springframework.test.web.servlet.setup.MockMvcBuilders;
@ExtendWith(MockitoExtension.class)
public class UserControllerTests {
@Mock
private UserService userService;
@InjectMocks
private UserController userController;
// HTTP 요청이 왔음을 가정해 주는 객체
private MockMvc mockMvc;
// 단위 테스트 이전에 mockMvc 가 초기화
@BeforeEach
public void beforeEach() {
// 컨트롤러로 userController 등록
mockMvc = MockMvcBuilders.standaloneSetup(userController).build();
// UserDto -> JSON
// JSON -> UserDto
// mock에서는 직렬화 역직렬화가 자동으로 안 됨
}
@Test
@DisplayName("UserDto를 나타내는 JSON 요청을 보내면 id가 null이 아닌 UserDto JSON 응답")
public void testCreate() throws Exception {
// given
// 1. userService.createUser에 전달할 UserDto 준비
String username = "huisu";
UserDto requestDto = new UserDto();
requestDto.setUsername(username);
// 2. userService.createUser가 반환할 UserDto 준비
Long userId = 1L;
UserDto responseDto = new UserDto();
requestDto.setUsername(responseDto.getUsername());
responseDto.setId(userId);
// 3. userService.creatUser의 동작 가정
when(userService.createUser(requestDto))
.thenReturn(responseDto);
// when
// perform: HTTP 요청을 보낸 것울 시뮬레이션하여 userController에게
ResultActions result = mockMvc.perform(
// 요청의 형태 (Body ...)를 빌더처럼 정의
// requestDto의 JSON일 것이야
post("/users")
.content(JsonUtil.toJson(requestDto))
.contentType(MediaType.APPLICATION_JSON));
// then
result.andExpectAll(
status().is2xxSuccessful(), // 성공적
content().contentType(MediaType.APPLICATION_JSON), // 응답이 JSON 형태
jsonPath("$.username", is(username)), // username은 요청한 값 그대로
jsonPath("$.id", notNullValue()) // id는 null이 아닌 값
);
}
}