JPA(Java Persistence API)

  • MyBatis(SQL Mapper) vs JPA(Object Relational Mapping)

    • 관계형 데이터베이스와 객체지향 프로그래밍 언어의 패러다임 차이

    • 관계형 데이터베이스는 데이터를 어떻게 저장할지에 초점을 맞춘 기술

      • 데이터베이스 쿼리 작성
      • 객체 모델링보다는 테이블 모델링에만 집중, 객체를 단순히 테이블에 맞추어 데이터 전달 역할만 하는 형태
      • 관계형 데이터베이스가 SQL만 인식 가능하기 때문에 각 테이블마다 기본적인 CRUD SQL를 매번 생성해야하는 상황
    • 객체지향 프로그래밍 언어는 메시지를 기반으로 기능과 속성을 한 곳에서 관리하는 기술

      • 상속, 1:N 등 다양한 객체 모델링을 데이터베이스로는 구현이 불가능
  • JPA

    • 서로 지향하는 바가 다른 2개 영역(객체지향 프로그래밍 언어와 관계형 데이터베이스)을 중간에서 패러다임을 일치를 시켜주기 위한 기술
    • 개발자는 객체지향적으로 프로그래밍을 하고, JPA가 이를 관계형 데이터베이스에 맞게 SQL을 대신 생성해서 실행

Spring Data JPA

  • JPA는 인터페이스로서 자바 표준명세서
    • 인터페이스인 JPA를 사용하기 위해서는 구현체가 필요하다.
      • 대표적으로 Hibernate, Eclipse Link 등
      • 구현체들을 좀 더 쉽게 사용하고자 추상화시킨 Spring Data JPA라는 모듈을 이용하여 JPA 기술을 다룬다.
      • JPA <- Hibernate <- Spring Data JPA
      • Spring 쪽에서는 Spring Data JPA를 개발하고 권장하고 있다.
      • Spring Data JPA가 등장한 이유
      • 구현체 교체의 용이성
        • Hibernate 외에 다른 구현체로 쉽게 교체하기 위함
        • Spring Data Redis를 사용하는 경우, Redis -> Jedis -> Lettuce로 쉽게 가능
      • 저장소 교체의 용이성
        • 관계형 데이터베이스 외에 다른 저장소로 쉽게 교체하기 위함
        • 관계형 데이터베이스에서 MongoDB로 교체가 필요한 경우 Spring Data JPA -> Spring Data MongoDB 의존성 교체로 사용가능
        • Spring Data의 하위 프로젝트들은 기본적인 CRUD의 인터페이스가 같기 때문이다.

Spring Data JPA 적용

  • spring-boot-starter-data-jpa와 com.h2database:h2 의존성 등록
    1. spring-boot-starter-data-jpa
      • 스프링 부트용 Spring Data JPA 추상화 라이브러리
      • 스프링 부트 버전에 맞춰 자동으로 JPA 관련 라이브러리들의 버전을 관리
    2. h2
      • 인메모리 관계형 데이터베이스
      • 별도의 설치가 필요없이 프로젝트 의존성만으로 관리할 수 없다.
      • 메모리에서 실행되기 때문에 어플리케이션을 재시작할 때마다 초기화된다는 점을 이용하여 테스트 용도로 사용

의존성 추가 및 확인

JPA 기능을 테스트 하기위한 기반 코드 작성

  • domain 패키지

    • 소프트웨어에 대한 요구사항 혹은 문제영역
    • xml에 쿼리를 담고, 클래스는 오로지 쿼리의 결과만 담던 일을 모두 도메인 클래스라고 불리는 곳에서 해결
  • Posts

    • 실제 DB의 테이블과 매칭될 클래스로 Entity 클래스라고 한다.
    • DB 데이터에 작업할 경우 실제 쿼리를 날리기보다, Entity 클래스의 수정을 통해 작업한다.
    1. JPA 어노테이션

      • @Entity

        • 테이블과 링크될 클래스

        • 기본값으로 클래스의 CamelCase 이름을 언더스코어 네이밍(_) 으로 테이블 이름을 매칭
          (SalesManager.java -> sales_manager)

        • 해당 클래스의 인스턴스 값들이 언제 어디서 변해야 하는지 코드상으로 명확하게 구분할 수 없기 때문에, 차후 기능 변경 시 복잡해 진다.

        • 그래서 Entity 클래스에서는 Setter 메서드를 만들지 않는다.

        • 대신 해당 필드의 값 변경이 필요할 경우 명확히 그 목적과 의도를 나타낼 수 있는 메서드를 추가

        • Setter가 없음에도 값을 채워 DB에 삽입할 수 있는 이유는 생성자 대신 @Builder를 통해 제공되는 빌더 클래스를 사용한다.

        • 생성자와 빌더의 차이

          • 생성자

            • 지금 채워야 할 필드가 무엇인지 명확히 지정할수 없다.

              public Example(String a, String b) {
                this.a = a;
                this.b = b;
              }
              new Example(b, a); // 로 호출하게 되는 경우 문제
          • 빌더

            • 필드별 set메서드를 제공하고 있어 명확히 구분된다.

              Example.builder()
                .a(a)
                .b(b)
                .build();
      • @Id

        • 해당 테이블 PK 필드를 나타낸다.
      • @GeneratedValue

        • PK의 생성 규칙
        • 스프링부트 2.0에서는 GenerationType.IDENTITY 옵션을 추가해야 auto_increment가 된다.
      • @Column

        • 테이블의 컬럼을 나타내며 굳이 선언하지 않더라도 해당 클래스의 필드는 모두 컬럼이 된다.
        • 사용하는 이유는, 기본 값 외에 추가로 변경이 필요한 옵션이 있으면 사용
        • 문자열의 경우 VARCHAR(255)가 기본값인데, 사이즈를 500으로 늘리고 싶은경우, 타입을 TEXT로 변경하고 싶은 경우 사용
    2. Lombok 어노테이션

      • @Getter

        • 클래스 내 모든 필드의 Getter 메서드를 자동생성
      • @NoArgsConstructor

        • 기본 생성자 자동 추가
        • public Posts() {} 와 같은 효과
      • @Builder

        • 해당 클래스의 빌더 패턴 클래스를 생성
        • 생성자 상단에 선언 시 생성자에 포함된 필드만 빌더에 포함
@Getter
@NoArgsConstructor
@Entity
public class Posts {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(length = 500, nullable = false)
    private String title;

    @Column(columnDefinition = "TEXT", nullable = false)
    private String content;

    private String author;

    @Builder
    public Posts(String title, String content, String author) {
        this.title = title;
        this.content = content;
        this.author = author;
    }
}
  • PostsRepository
    • JpaRepository를 상속받은 PostsRepository 인터페이스를 생성
    • MyBatis등에서 Dao라 불리는 DB Layer로 JPA에서는 Repository라 부른다.
    • JpaRepositoy<Entity 클래스, PK 타입> 를 상속하면 기본적인 CRUD 메서드가 자동으로 생성된다.
    • @Repository를 추가할 필요가 없다.
    • 다만, Entity 클래스와 기본 Entity Repository 클래스는 같은 위치(domain 패키지)에 있어야 한다.
    • Entity 클래스는 기본 Repositorty 없이 제대로된 역할을 할 수 없다.
public interface PostsRepository extends JpaRepository<Posts, Long> {
}

Spring Data JPA 테스트 코드 작성

  • PostsRepositoryTest 클래스
    1. @SpringBootTest
      • 해당 어노테이션을 선언하는 경우 H2 데이터베이스를 자동으로 실행
      • 테스트도 H2 데이터베이스를 기반으로 실행된다.
    2. @After
      • Junit에서 단위 테스트가 끝날 때마다 수행되는 메서드를 지정
      • 보통 배포 전 전체 테스트를 수행할 때 테스트간 데이터 침범을 막기 위해서 사용
      • 여러 테스트가 동시에 수행되면 테스트용 데이터베이스인 H2에 데이터가 그대로 남아 있어 다음 테스트 실행 시 테스트 실패할 수 있다.
    3. postsRepository.save
      • 테이블 posts에 insert/update 쿼리를 실행
      • id 값이 있다면 update, id 값이 없다면 insert 쿼리가 실행된다.
    4. postsRepository.findAll
      • 테이블 posts에 있는 모든 데이터를 조회해오는 메서드
@RunWith(SpringRunner.class)
@SpringBootTest
public class PostsRepositoryTest {

    @Autowired
    PostsRepository postsRepository;

    @After
    public void cleanup() {
        postsRepository.deleteAll();
    }

    @Test
    public void getBoard() {
        // given
        String title = "테스트 게시글";
        String content = "테스트 본문";

        postsRepository.save(
                Posts.builder()
                .title(title)
                .content(content)
                .author("seok@gmail.com")
                .build()
        );

        // when
        List<Posts> postsList = postsRepository.findAll();

        // then
        Posts posts = postsList.get(0);
        Assertions.assertThat(posts.getTitle()).isEqualTo(title);
        Assertions.assertThat(posts.getContent()).isEqualTo(content);
    }
}

쿼리로그 확인 방법

  • src/main/resources 경로의 application.properties 파일에 설정 추가
# jpa setting
spring.jpa.show_sql=true

spring.jpa.show_sql=true 설정

  • create table 쿼리에 id bigint generated by default as identity라는 옵션으로 생성
    • 이는 H2의 쿼리 문법이 적용되었기 때문이다.
    • H2 쿼리 문법에서 MySQL 버전으로 변경
# jpa setting
spring.jpa.show_sql=true
# change QueryLog format from h2 to mysql
spring.jpa.properties.hibernate.dialect=org.hibernate.dialect.MySQL5InnoDBDialect

  • id bigint not null auto_increment로 변경됨을 확인

Lombok 설정 및 테스트

  • VO(DTO) 생성 시 Getter, Setter, Contructor, toString 등을 어노테이션으 자동 생성

build.gradle dependency 추가

  • lombok 의존성 추가
dependencies {
    compile('org.springframework.boot:spring-boot-starter-web')
    compile("org.projectlombok:lombok")
    testCompile('org.springframework.boot:spring-boot-starter-test')
}    

lombok plugin 설치

  • lombok plugin 설치

lombok 설정

  • lombok 플러그인은 한 번만 설치
  • build.gradle에 라이브러리 추가와 Enable annotation.processing체크는 프로젝트마다 설정해야 한다.

lombok으로 Refactoring

  • web 패키지에 dto 패키지를 추가

com.seok.sample.web.dto.HelloResponseDto 추가

  • dto 패키지에 HelloResponseDto 추가

    1. @Getter

      • 선언된 모든 필드의 get 메서드를 생성
    2. @RequiredArgsContructor

      • 선언된 모든 final 필드가 포함된 생성자를 생성

      • final이 없는 필드는 생성자에 포함되지 않는다.

@Getter
@RequiredArgsConstructor
public class HelloResponseDto {
    private final String name;
    private final int amount;
}

lombok 테스트

  • 테스트 코드

    1. assertThat
      • assertj라는 테스트 검증 라이브러리의 검증 메서드
      • 검증하고 싶은 대상을 메서드 인자로 받는다.
      • 메서드 체이닝이 지원되어 isEqualTo와 같이 메서드를 이어서 사용할 수 있다.
    2. isEqualTo
      • assertj의 동등 비교 메서드
      • assertThat에 있는 값과 isEqualTo의 값을 비교해서 같은 경우 성공
  • assetj vs Junit

    • CoreMatchers와 달리 추가적으로 라이브러리가 필요하지 않다.
      • Junit의 assertThat을 쓰게 되면 is()와 같이 CoreMatchers 라이브러리가 필요하다.
    • 자동완성이 좀 더 확실하게 지원
      • IDE에서는 CoreMatchers와 같은 Matcher 라이브러리의 자동완성 지원이 약하다.
  • HelloResponseDtoTest

    • given, when, then의 순서로 테스트 코드를 작성
    1. Given
      • HelloResponseDto 클래스에 생성자로 주입될 값을 설정
      • 테스트 기반 환경을 구축하는 단계
    2. When
      • HelloResponseDto 클래스 생성 및 초기화
      • 테스트 하고자 하는 행위 선언
    3. Then
      • 테스트의 결과를 검증
      • assertThat 메서드를 통해 HelloResponseDto instance의 name, amount의 값을 확인
      • assertThat 성공으로 lombok의 @Getter를 통해 get 메서드, @RequiredArgsContructor로 생성자가 자동으로 생성
import org.assertj.core.api.Assertions;
import org.junit.Test;

public class HelloResponseDtoTest {
    @Test
    public void lombok_test() {
        // Given
        String name = "test";
        int amount = 1000;
        // when
        HelloResponseDto dto = new HelloResponseDto(name, amount);
        // then
        Assertions.assertThat(dto.getName()).isEqualTo(name);
        Assertions.assertThat(dto.getAmount()).isEqualTo(amount);
    }
}

HelloController에 ResponseDto 사용

  • HelloController
    • @RequestParam
      • 외부에서 API로 넘긴 파라미터를 가져오는 어노테이션
      • name (@RequestParam("name"))이란 이름으로 넘긴 파라미터를 메서드 파라미터 name(String name)에 저장
@RestController
public class HelloController {

    ...

    @GetMapping("/hello/dto")
    public HelloResponseDto helloDto(
            @RequestParam("name") String name,
            @RequestParam("amount") int amount) {
        return new HelloResponseDto(name, amount);
    }

}

HelloController 테스트

  • HelloControllerTest
    1. param
      • API 테스트 할 때 요청 파라미터를 설정
      • 단, 그 값은 String만 허용
      • 숫자/날짜 등의 데이터도 등록하는 경우 문자열로 변경이 필요 (String.valueOf(value))
    2. jsonPath
      • JSON 응답값을 필드별로 검증할 수 있는 메서드
      • $를 기준으로 필드명을 명시
      • 여기서는 name, amount를 검증하니 $.name, $.amount로 검증
@RunWith(SpringRunner.class)
@WebMvcTest
public class HelloControllerTest {

    @Autowired
    private MockMvc mvc;

    ...

    @Test
    public void return_helloDto() throws Exception {
        String name = "hello";
        int amount = 1000;

        mvc.perform(
                get("/hello/dto")
                .param("name", name)
                .param("amount", String.valueOf(amount))
        )
        .andDo(print())
        .andExpect(status().isOk())
        .andExpect(jsonPath("$.name", is(name)))
        .andExpect(jsonPath("$.amount", is(amount)));
    }
}
  • 결과 테스트
    • MockHttpServletResponse.Body
    MockHttpServletResponse:
           Status = 200
    Error message = null
          Headers = [Content-Type:"application/json;charset=UTF-8"]
     Content type = application/json;charset=UTF-8
             Body = {"name":"hello","amount":1000}
    Forwarded URL = null
   Redirected URL = null
          Cookies = []

단위테스트

  • 단위테스트 vs TDD

    • TDD: 테스트가 주도하는 개발 (레드 그린 사이클)

      1. 항상 실패하는 테스트 먼저 작성 (Red)
      2. 테스트가 통과하는 프로덕션 코드 작성 (Green)
      3. 테스트가 통과하면 프로덕션 코드를 리펙토링 (Refactor)
    • 단위테스트: 기능 단위의 테스트 코드를 작성하는 것 (순수하게 테스트 코드를 작성하는 것)

  • 단위 테스트의 장점

    • 단위 테스트는 개발 단계 초기에 문제를 발견하게 도와준다.
    • 단위 테스트는 개발자가 나중에 코드를 리펙토링하거나 라이브러리 업그레이드 등에서 기존 기능이 올바르게 작동하는지 확인할 수 있다.
    • 단위 테스트는 기능에 대한 불확실성을 감소시킬 수 있다.
    • 단위 테스트는 시스템에 대한 실제 문서를 제공한다.
      (즉, 단위 테스트 자체가 문서로 사용할 수 있다.)

스프링 부트 실행 Application 클래스 작성

  • @SpringBootApplication

    • 프로젝트 최상단에 위치하는 클래스
    • 스프링 부트는 @SpringBootApplication이 있는 위치부터 설정을 읽어간다.
    • 스프링 부트의 자동설정, 스프링 Bean 읽기와 생성을 자동으로 설정
  • SpringApplication.run

    • 내장 WAS (Web Application Server, 웹 어플리케이션 서버) 실행
    • 스프링 부트로 만들어진 Jar 파일(실행 사능한 Java 패키징 파일)로 실행 가능
  • 내장 WAS를 사용하는 이유

    • 항상 서버에 톰캣을 설치할 필요가 없다.
    • 언제 어디서나 같은 환경에서 스프링 부트를 배포할 수 있다.
    • 외부 WAS를 쓸 경우 모든 서버는 WAS의 종류와 버전, 설정을 일치시켜야 한다.
@SpringBootApplication
public class Application {
    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }
}

컨트롤러 관련 클래스를 저장할 패키지 생성

  • 패키지 및 컨트롤러 생성
    • web
    • HelloController
      • @RestController
        • 컨트롤러를 JSON 데이터 타입을 반환하는 컨트롤러로 설정
        • 기존 Spring Framework의 경우 @ResponseBody를 각 메서드에 선언
      • @GetMapping
        • Http Method인 Get의 요청을 받을 수 있는 API 설정
        • 기존 Spring Framework의 경우 @RequestMapping(method= RequestMethod.GET)으로 사용
        • "/hello"로 요청이 오는 경우 문자열 hello을 반환
@RestController
public class HelloController {
    @GetMapping("/hello")
    public String hello() {
        return "hello";
    }
}

Test API 작성

  • HelloController를 테스트 할 HelloControllerTest 클래스 작성
    1. @RunWith(SpringRunner.class)
      • 테스트를 진행할 때 JUnit에 내장된 실행자 외에 다른 실행자를 실행
      • SpringRunner는 스프링 실행자
      • 즉, 스프링 부트 테스트와 JUnit 사이에 연결자 역할을 한다.
    2. @WebMvcTest
      • 여러 스프링 테스트 어노테이션 중, Web(Spring MVC)에 집중할 수 있는 어노테이션
      • @Controller, @ControllerAdvice 등을 사용할 수 있다.
      • @Service, @Component, @Repository 등은 사용할 수 없다.
    3. @Autowired
      • 스프링이 관리하는 빈(Bean)을 주입
    4. MockMvc mvc
      • 웹 API 테스트 시 사용
      • 스프링 MVC 테스트의 시작점
      • HTTP GET, POST 등에 대한 API를 테스트 할 수 있다.
    5. mvc.perform(get("/hello"))
      • MockMvc를 통해 /hello 주소로 Http GET 요청 가능
      • 체이닝을 지원하여 여러 검증 기능을 이어서 선언할 수 있다.
    6. .andExcept(status().isOk())
      • mvc.perform의 결과를 검증
      • HTTP Header의 Status를 검증
    7. .andExcept(content().string(hello))
      • mvc.perform의 결과를 검증
      • 응답 본문의 내용을 검증
    8. .andDo(print())
      • MockHttpServletRequest
      • Handler
      • Async
      • Resolved Exception
      • ModelAndView
      • FlashMap
      • MockHttpServletResponse 등의 내용의 결과 값을 확인 할 수 있다.
@RunWith(SpringRunner.class)
@WebMvcTest
public class HelloControllerTest {

    @Autowired
    private MockMvc mvc ;

    @Test
    public void return_hello() throws Exception {
        String hello = "hello";

        mvc.perform(get("/hello"))
                .andDo(print())
                .andExpect(status().isOk())
                .andExpect(content().string(hello));
    }
}

테스트 코드 검증

  • 테스트 코드 결과 값 확인

수동 실행으로 검증 (이슈)

  • 오라클 설치로 인한 포트 중복 이슈

  • SpringBoot 실행 시 Apache Tomcat의 기본 포트는 8080이기 때문에 포트를 변경하여 실행

application.properties 파일 생성

  • application.properties 파일 내에 apache tomcat port 수정을 위한 설정
# server setting
server.port=8085

port 중복으로 인한 이슈 처리완료 및 /hello URL에 접근하여 "hello" 확인

SpringBoot 실행 로그 확인
URL 접근하여 페이지 확인

IntelliJ로 SpringBoot프로젝트 생성하기

  1. Gradle Java 프로젝트 생성
  2. Gradle 버전 정보 수정하기
  3. Gradle 프로젝트를 SpringBoot 프로젝트로 Convert하기

Gradle Java 프로젝트 생성

  • 프로젝트 유형선택
    • Gradle 선택

프로젝트 유형 선택 (Gradle)

  • 프로젝트 location 선택 및 GroupId, ArtifactId 작성
    • 프로젝트 명과 ArtifactId는 같은 값으로 설정되어야 함

디렉토리 위치 선택 및 프로젝트명 작성

  • 프로젝트 생성
    • Gradle을 통해 build

프로젝트 생성 및 빌드

Gradle 버전 변경

  • 2020.05.27 일자로 프로젝트 생성 시 Gradle 6.1 버전이 설치되는데 이를 프로젝트의 원할한 진행을 위해 4.8로 downgrade 하도록 한다.
    • 이후에 lombok 사용 시 오류가 발생 할 수 있다.

Gradle 버전 확인

  • Gradle 변경 명령어

$ gradlew wrapper --gradle-version 4.10.2

Gradle 버전 확인

  • Gradle 버전 downgrade 후 확인

Gradle 프로젝트를 SpringBoot 프로젝트로 변경하기

  • build.gradle 파일 확인

SpringBoot으로 변경하기 위해 설정하기

  • SpringBootVersion 정보 설정하기 (ext)
    • ext 키워드를 통해 전역변수 설정
    ext {
        springBootVersion = '2.1.9.RELEASE'
    }
  • 프로젝트 개발에 필요한 의존성들을 선언하기 (dependencies)
    dependencies {
        classpath("org.springframework.boot:spring-boot-gradle-plugin:${springBootVersion}")
        testCompile('org.springframework.boot:spring-boot-starter-test')
    }
  • 플로그인 의존성 적용을 위한 필수 플로그인 설정
    • io.spring.dependency-management 플러그인은 스프링 부트의 의존성들을 관리해주는 플러그인으로 중요
apply plugin: 'java'
apply plugin: 'eclipse'
apply plugin: 'org.springframework.boot'
apply plugin: 'io.spring.dependency-management'
  • build.gradle 설정 완료
buildscript {
    ext {
        springBootVersion = '2.1.9.RELEASE'
    }
    repositories {
        mavenCentral()
        jcenter()
    }
    dependencies {
        classpath("org.springframework.boot:spring-boot-gradle-plugin:${springBootVersion}")
    }
}

apply plugin: 'java'
apply plugin: 'eclipse'
apply plugin: 'org.springframework.boot'
apply plugin: 'io.spring.dependency-management'

group 'com.seok'
version '1.0-SNAPSHOT'

repositories {
    mavenCentral()
    jcenter()
}

dependencies {
    compile('org.springframework.boot:spring-boot-starter-web')
    testCompile('org.springframework.boot:spring-boot-starter-test')
}

Gradle 설정 확인

  • 우측의 Gradle 모듈 탭을 눌러 Dependencies를 확인

jcenter vs mavenCentral

  • repositories는 각종 의존성(라이브러리)들을 어떤 원격 저장소에서 받을지 정하게 된다.
  • 이 저장소의 역할을 mavenCentral과 jcenter가 한다.
  • mavenCentral은 본인이 만든 라이브러리를 업로드하기 위해서 많은 과정과 설정이 필요하다.
  • jcenter는 이런 문제점을 개선하여 라이브러리 업로드를 간단하게 한다.
  • jcenter에 라이브러리를 업로드하면 mavenCentral에도 업로드될 수 있도록 자동화 할 수 있다.

Spring4 & MyBatis

[부스트코스] 웹 프로그래밍 기반의 설정에서 추가 설정으로 확장하기 위한 포스팅

  • 목표

    • spring4 pom.xml 설정
    • mybatis dependency 추가
    • mybatis java config
    • domain, mapper, sql 샘플 작성
    • mapper 테스트
  • Spring4의 Java Config 향상 기능을 통해 Mybatis를 구성하는 xml 제외하기

  • mybatis-spring 라이브러리에서 제공하는 @MapperScan 어노테이션을 사용하여 MyBatis Domain Mapper에 대해 패키지단위로 검색이 가능하다.

  • Servlet 3+와 결합하는 경우 XML없이 응용 프로그램을 구성하고 실행할 수 있다.

프로젝트 스펙 및 설정 구조

모듈 버전 설명
Spring Framework 4.3.15.RELEASE
MyBatis 3.5.2
mybatis-spring 2.0.2
- src/main
    - java/com/seok/mybatis/
                    config/
                        * AppConfig.java
                        * DBConfig.java
                        * MybatisConfig.java
                    domain/
                        * Product.java
                    persistence/
                        * ProductMapper.java
    - resources/mapper/
            * ProductMapper.xml
* pom.xml

프로젝트 구조

설정

  • pom.xml

    • MyBatis 사용을 위한 mybatis, mybatis-spring dependency를 추가 한다.

    • 물론 DB를 사용하기 위한 프로젝트이기 때문에 spring-jdbc, mysql-connector-java도 추가

    <dependency>
        <groupId>org.springframework</groupId>
        <artifactId>spring-context</artifactId>
        <version>${spring.version}</version>
    </dependency>

    <!-- https://mvnrepository.com/artifact/org.springframework/spring-jdbc -->
    <dependency>
        <groupId>org.springframework</groupId>
        <artifactId>spring-jdbc</artifactId>
        <version>${spring.version}</version>
    </dependency>

    <!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java -->
    <dependency>
        <groupId>mysql</groupId>
        <artifactId>mysql-connector-java</artifactId>
        <version>5.1.45</version>
    </dependency>

    <!-- https://mvnrepository.com/artifact/org.mybatis/mybatis -->
    <dependency>
        <groupId>org.mybatis</groupId>
        <artifactId>mybatis</artifactId>
        <version>3.5.2</version>
    </dependency>

    <!-- https://mvnrepository.com/artifact/org.mybatis/mybatis-spring -->
    <dependency>
        <groupId>org.mybatis</groupId>
        <artifactId>mybatis-spring</artifactId>
        <version>2.0.2</version>
    </dependency>
  • AppConfig.java
    • 스프링 설정 클래스
    • DBConfig와 MyBatisConfig를 분리해서 Import하였다.
    • 같은 클래스안에서 설정해도 무관

@Configuration
@Import({DBConfig.class, MybatisConfig.class})
public class AppConfig {
}
  • DBConfig.java
    • DB 설정관련 클래스
    • java 파일 내에 설정 정보를 넣지 않고 properties 파일을 사용하여 보안 및 배포 관리

@Configuration
@EnableTransactionManagement
@PropertySource({ "classpath:db.properties" })
public class DBConfig implements TransactionManagementConfigurer {

    @Value("${spring.datasource.driver-class-name}")
    private String driverClassName;

    @Value("${spring.datasource.url}")
    private String url;

    @Value("${spring.datasource.username}")
    private String userName;

    @Value("${spring.datasource.password}")
    private String password;

    @Override
    public PlatformTransactionManager annotationDrivenTransactionManager() {
        return transactionManager();
    }

    @Bean
    public PlatformTransactionManager transactionManager() {
        return new DataSourceTransactionManager(dataSource());
    }

    @Bean
    public DataSource dataSource() {
        BasicDataSource dataSource = new BasicDataSource();
        dataSource.setDriverClassName(driverClassName);
        dataSource.setUrl(url);
        dataSource.setUsername(userName);
        dataSource.setPassword(password);
        return dataSource;
    }
}
  • MybatisConfig.java

    1. line 2: MyBatis Mapper가 있는 패키지 설정
    2. line 9: MyBatis.xml 파일에서 resultType으로 사용할 수 있는 도메인 개체를 포함하는 패키지 설정
      (SQL쿼리에서 Java 객체를 반환하는 것은 ORM 문제를 해결)
    • MyBatis를 설정하기 위해 SqlSessionFactoryBean를 사용

@Configuration
@MapperScan("com.seok.mybatis.persistence")
public class MybatisConfig {

    @Bean
    public SqlSessionFactoryBean sqlSessionFactoryBean(DataSource dataSource) throws IOException {
        SqlSessionFactoryBean sessionFactory = new SqlSessionFactoryBean();
        sessionFactory.setDataSource(dataSource);
        sessionFactory.setTypeAliasesPackage("com.seok.mybatis.domain");
        sessionFactory.setMapperLocations(new PathMatchingResourcePatternResolver().getResources("classpath:mapper/*.xml"));
        return sessionFactory;
    }
}

  • Product.java
    • Product 도메인 객체는 실제 단순한 POJO

public class Product implements Serializable{

    private static final long serialVersionUID = 3690807750019415954L;

    private int id;
    private int categoryId;
    private String desc;
    private String content;
    private String event;
    // constructor, setter, getter

}
  • ProductMapper.java
    • Mapper 클래스는 해당 mapper.xml에 정의된 sql문과 일치하는 메서드를 정의하는 단순한 인터페이스이다.
    • xml로 SQL을 정의하는 대신 어노테이션으로 간단한 SQL문을 작성하는 것이 가능하지만, query가 번거로워져 복잡한 Query는 사용하지 않는다.

import org.apache.ibatis.annotations.Select;
import kr.or.seok.naver.domain.Product;

public interface ProductMapper {

    public List<Product> getAllProducts();

    // Simple SQL
    @Select("SELECT COUNT(*) totalCnt FROM product")
    public int getTotalCnt();

}

<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="com.seok.mybatis.persistence.ProductMapper">
    <cache />

    <select id="getAllProducts" resultType="Product">
        SELECT 
            id, 
            category_id, 
            description, 
            content, 
            event 
        FROM product
    </select>

</mapper>

테스트

  • TestMyBatis.java
    • Test 코드는 Mockito나 Junit을 사용하는 것이 편리

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(classes = AppConfig.class)
public class TestMyBatis {

    @Autowired
    ProductMapper prodMapper;

    @Test
    public void testMapper() {
        // prodMapper.getAllProducts();

    }

    @Test
    public void testTotalProducts() {
        // productMapper.getTotalCnt();
    }
}

결과

  • TotalCnt()
    • Product의 전체 row 갯수를 확인하기 위한 메서드로 50개가 조회되고 있음을 알 수 있다.

23:53:03.208 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getTotalCnt - ==>  Preparing: SELECT COUNT(*) totalCnt FROM product 
23:53:03.251 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getTotalCnt - ==> Parameters: 
23:53:03.276 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getTotalCnt - <==      Total: 1
23:53:03.282 [main] DEBUG org.mybatis.spring.SqlSessionUtils - Closing non transactional SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession@3daf7722]
23:53:03.282 [main] DEBUG org.springframework.jdbc.datasource.DataSourceUtils - Returning JDBC Connection to DataSource
23:53:03.336 [main] INFO com.seok.mybatis.config.TestMyBatis - 50
  • getAllProducts()
    • Product의 모든 row를 조회하기 위한 테스트 메서드로 50개의 Product리스트가 조회되고 있음을 확인할 수 있다.

23:53:03.348 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getAllProducts - ==>  Preparing: SELECT id, category_id, description, content, event FROM product 
23:53:03.348 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getAllProducts - ==> Parameters: 
23:53:03.372 [main] DEBUG com.seok.mybatis.persistence.ProductMapper.getAllProducts - <==      Total: 50
23:53:03.379 [main] DEBUG org.mybatis.spring.SqlSessionUtils - Closing non transactional SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession@52066604]
23:53:03.379 [main] DEBUG org.springframework.jdbc.datasource.DataSourceUtils - Returning JDBC Connection to DataSource
23:53:03.419 [main] INFO com.seok.mybatis.config.TestMyBatis - [ {
    "id" : 1,
    "categoryId" : 0,
    "desc" : null,
    "content" : "",
    "event" : ""
    },
    ...
}] 

깊이 우선 탐색

  • 깊이 우선 탐색 개념

    • 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
    • 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 탐색
    • 해당 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.
    • 모든 노드를 방문하고자 하는 경우에 선택
    • 깊이 우선 탐색(DFS)가 너비 우선 탐색(BFS)보다 간단하다.
    • 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.
  • 깊이 우선 탐색(DFS)의 특징

    • 순환 알고리즘의 형태를 갖고 있다.
    • 전위 순회(Pre-Order)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
    • 그래프 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사한다.

코드 설계

  • 시작 노드(1)로부터 인접 노드(2, 3)를 모두 방문
  • 인접 노드(2, 3)를 스택에 넣고 방문처리
  • 시작 노드(1)로부터 인접한 노드 중에 방문하지 않은 노드가 더이상 없는 경우
  • 이전의 위치로 돌아와 찾아가지 않은 다른 길로 탐색한다.

코드 구현

  • 순환 호출을 이용한 DFS 구현
    public class DFSList {

     static class Graph {
         private int V;
         private LinkedList<Integer>[] adjacent;

         @SuppressWarnings("unchecked")
         public Graph(int V) {
             this.V = V;
             this.adjacent = new LinkedList[V];
             for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
         }

         public void addEdge(Graph graph, int src, int dest) {
             graph.adjacent[src].add(dest);
             graph.adjacent[dest].add(src);
         }

         public void printGraph(Graph graph) {
             for (int v = 1; v < graph.V; v++) {
                 System.out.println("Node [" + v + "]");
                 System.out.print("adjacent Node: ");
                 for (Integer node : graph.adjacent[v]) {
                     System.out.print("[" + node + "]\t");
                 }
                 System.out.println();
             }
         }

         /**
          * 비연결형 그래프의 경우, 모든 정점을 하나씩 방문하는 너비 우선 탐색
          * @param start
          */
         public void dfs() {
             boolean[] visit = new boolean[V];

             for(int i = 1 ; i < V ; i++) {
                 if(visit[i] == false) 
                     dfsUtil(i, visit);
                 System.out.println();
             }
         }

         /**
          * 주어진 노드를 시작한 너비 우선 탐색
          * @param start
          */
         public void dfs(int start) {
             boolean[] visit = new boolean[V];
             dfsUtil(start, visit);
             System.out.println();
         }

         /**
          * 인접한 노드 방문 하는 DFS 재귀함수
          * @param start
          * @param visit
          */
         private void dfsUtil(int start, boolean[] visit) {
             visit[start] = true; // 방문 체크
             System.out.print(start + "\t");

             Iterator<Integer> it = adjacent[start].listIterator(); // 인접한 노드 리스트
             while(it.hasNext()) {
                 int n = it.next();
                 if(!visit[n]) // 방문 확인 false인 경우, 노드 탐색
                     dfsUtil(n, visit);
             }
         }
     }

     public static void main(String[] args) {
         int initSize = 8;

         Graph graph = new Graph(initSize);

         graph.addEdge(graph, 1, 2);
         graph.addEdge(graph, 1, 3);
         graph.addEdge(graph, 2, 3);
         graph.addEdge(graph, 2, 4);
         graph.addEdge(graph, 2, 5);
         graph.addEdge(graph, 3, 6);
         graph.addEdge(graph, 3, 7);
         graph.addEdge(graph, 4, 5);
         graph.addEdge(graph, 6, 7);

         graph.printGraph(graph);

         graph.dfs(4); /* 주어진 노드를 기준으로 BFS 탐색 */
         graph.dfs();
     }
    }
  • Graph의 각 노드에 연결된 노드 리스트 및 DFS 결과
    // 노드별 연결 리스트 확인
    Node [1]
    adjacent Node: [2]    [3]    
    Node [2]
    adjacent Node: [1]    [3]    [4]    [5]    
    Node [3]
    adjacent Node: [1]    [2]    [6]    [7]    
    Node [4]
    adjacent Node: [2]    [5]    
    Node [5]
    adjacent Node: [2]    [4]    
    Node [6]
    adjacent Node: [3]    [7]    
    Node [7]
    adjacent Node: [3]    [6]    
    // 주어진 노드를 기준으로 DFS 탐색
    4    2    1    3    6    7    5    
    // 모든 노드 탐색
    1    2    3    6    7    4    5    

분석

  • 깊이 우선 탐색(DFS)의 시간 복잡도
    • 인접 리스트로 표현된 그래프: O(N+E)
    • 인접 행렬로 표현된 그래프: O(N^2)

너비 우선 탐색

  • 루트노드(또는 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

    • 시작 정점(노드)으로부터 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
  • 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

    • 맹목적 탐색방법이란 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법
  • 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용

  • 너비 우선 탐색 알고리즘의 장점

    • 너비 우선 탐색은 출발노드에서 목표노드까지의 최단 길이 경로를 보장
  • 너비 우선 탐색 알고리즘의 단점

    • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
      • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
      • 무한 그래프(infinite graph)의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.

코드 설계

  • 기준이 되는 노드의 상위 노드 검색, 없을 경우 인접 노드 검색
  • 같은 레벨의 노드 검색 후, 해당 레벨 + 1의 인접 노드 검색
  • 리스트를 확인할 수 있는 Queue, 방문 확인을 위한 visit 배열 생성
  • 사용자가 입력한 기준 값으로 queue 넣고 해당 queue의 node 값에 인접한 adjacent node 리스트를 검색하여 방문 표시

코드 구현

  • 인접행렬을 기반으로 한 너비 우선 탐색
public class GraphArr {

    private int[][] MATRIX; // 그래프 배열 선언

    public GraphArr() {}

    public GraphArr(int initSize) {
        this.MATRIX = new int[initSize + 1][initSize + 1];
    }

    public void put(int x, int y) {
        MATRIX[x][y] = MATRIX[y][x] = 1;
    }

    public void printGraph() {
        for (int i = 0; i < MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[i].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 너비 우선 탐색
     * @param V
     */
    private void bfs(int V) {

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[MATRIX.length]; // 간선 갯수

        queue.offer(V);
        visit[V] = true;

        while(!queue.isEmpty()) {
            int x = queue.poll(); // 방문한 노드를 큐에서 꺼내 인접한 모든 노드를 조회
            System.out.print(x + "\t");
            for(int i = 0 ; i < MATRIX.length ; i++) {

                if(!visit[i] && MATRIX[x][i] == 1) { // 간선확인, 노드 방문 여부 확인
                    visit[i] = true;
                    queue.offer(i);
                }
            }
        }
    }

    public static void main(String[] args) {

        int initSize = 7;

        GraphArr graph = new GraphArr(initSize);

        graph.put(1, 2);
        graph.put(1, 3);
        graph.put(2, 3);
        graph.put(2, 4);
        graph.put(2, 5);
        graph.put(3, 6);
        graph.put(3, 7);
        graph.put(4, 5);
        graph.put(6, 7);

        graph.printGraph();
        graph.bfs(1); /* 주어진 노드를 기준으로 BFS 탐색 */
    }
}
  • 인접 배열 출력 및 BFS 탐색 결과
// 배열 출력
0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 
0 1 0 1 1 1 0 0 
0 1 1 0 0 0 1 1 
0 0 1 0 0 1 0 0 
0 0 1 0 1 0 0 0 
0 0 0 1 0 0 0 1 
0 0 0 1 0 0 1 0 
// BFS 탐색
1    2    3    4    5    6    7    
  • 인접 리스트를 기반으로 한 너비 우선 탐색
public class GraphList {

    static class Graph {
        private int V;
        private LinkedList<Integer>[] adjacent;

        @SuppressWarnings("unchecked")
        public Graph(int V) {
            this.V = V;
            this.adjacent = new LinkedList[V];
            for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
        }

        public void addEdge(Graph graph, int src, int dest) {
            graph.adjacent[src].add(dest);
            graph.adjacent[dest].add(src);
        }

        public void printGraph(Graph graph) {
            for (int v = 1; v < graph.V; v++) {
                System.out.println("Node [" + v + "]");
                System.out.print("adjacent Node: ");
                for (Integer node : graph.adjacent[v]) {
                    System.out.print("[" + node + "]\t");
                }
                System.out.println();
            }
        }

        /**
         * 너비 우선 탐색
         * @param start
         */
        public void bfs(int start) {
            boolean[] visit = new boolean[V];
            LinkedList<Integer> queue = new LinkedList<>();

            visit[start] = true;
            queue.offer(start);

            while(!queue.isEmpty()) {
                start = queue.poll();
                System.out.print(start + "\t");

                Iterator<Integer> i = adjacent[start].listIterator();
                while(i.hasNext()) {
                    int n = i.next();
                    if(!visit[n]) {
                        visit[n] = true;
                        queue.offer(n);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int initSize = 8;

        Graph graph = new Graph(initSize);

        graph.addEdge(graph, 1, 2);
        graph.addEdge(graph, 1, 3);
        graph.addEdge(graph, 2, 3);
        graph.addEdge(graph, 2, 4);
        graph.addEdge(graph, 2, 5);
        graph.addEdge(graph, 3, 6);
        graph.addEdge(graph, 3, 7);
        graph.addEdge(graph, 4, 5);
        graph.addEdge(graph, 6, 7);

        graph.printGraph(graph);

        graph.bfs(1); /* 주어진 노드를 기준으로 BFS 탐색 */
    }
}
  • 인접 리스트 출력 및 BFS 탐색 결과
// 기준 노드 및 인접 노드 출력
Node [1]
adjacent Node: [2]    [3]    
Node [2]
adjacent Node: [1]    [3]    [4]    [5]    
Node [3]
adjacent Node: [1]    [2]    [6]    [7]    
Node [4]
adjacent Node: [2]    [5]    
Node [5]
adjacent Node: [2]    [4]    
Node [6]
adjacent Node: [3]    [7]    
Node [7]
adjacent Node: [3]    [6]    
// BFS 탐색 1 기준
1    2    3    4    5    6    7

분석

  • 인접 리스트 시간 복잡도
    • O(N+E)
  • 인접 행렬 시간 복잡도
    • O(N^2)
  • 그래프 내에 적은 숫자의 간선만을 갖는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리

그래프

  • 개념

    • 단순히(node, N)와 그 노드를 연결하는 간선(edge, E)을 하나로 모아 놓은 자료구조
    • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
  • 용어

    • 정점(vertex): 위치라는 개념. (node 라고도 부름)
    • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
    • 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
    • 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
    • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
    • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
    • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
    • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
    • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
    • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
    • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
  • 특징

    • 그래프는 네트워크 모델이다.
    • 2개 이상의 경로가 가능하다.
    • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
    • self-loop 뿐 아니라 loop/circuit 모두 가능하다.
    • 루트 노드라는 개념이 없다.
    • 부모-자식 관계라는 개념이 없다.
    • 순회는 DFS나 BFS로 이루어진다.
    • 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
    • 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
    • 간선의 유무는 그래프에 따라 다르다.
    • 해당 자료구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다.
    • 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하지만, 실제 적용에 있어서 최적의 자료구조는 두 구조의 조합된 형태를 띤다.
  • 종류

    • 무방향 그래프 & 방향 그래프
    • 가중치 그래프(Weighted Graph)
    • 연결 그래프 & 비연결 그래프
    • 사이클(Cycle) & 비순환 그래프(Acyclic Graph)
    • 완전 그래프(Complete Graph)
  • 구현방법 2가지

    1. 인접 리스트(Adjacency List)

      • 모든 정점(vertex) 및 노드(Node)를 리스트(ArrayList, LinkedList)에 저장. 즉, 각각의 노드에 인접한 노드들을 저장
      • 정점 index를 통해 각 노드에 인접한 노드 리스트를 확인할 수 있다.
      • 무방향 그래프에서는 간선이 인접한 노드에 모두 저장되기 때문에 두번 저장된다.
        ex) 정점의 수: N, 간선의 수:E인 무방향 그래프인 경우
        N개의 리스트, N개의 배열, 2E개의 노드가 필요
    2. 인접 배열(Adjacency Matrix)

      • 정점 혹은 노드의 개수가 N인 그래프를 인접 행렬로 표현
      • 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요
      • 무방향 그래프를 인접 행렬로 표현한다면, 대칭 행렬이 된다.
      • 인접 리스트의 경우 인접한 노드의 리스트를 갖고 있기 때문에 인접한 노드를 쉽게 찾을 수 있지만, 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.
  • 인접 리스트와 인접 행렬의 용도 차이

    1. 인접 리스트
      • 그래프 내에 적은 숫자의 간선만을 갖는 희소 그래프(Sparse Graph)인 경우
      • 어떤 노드에 인접한 노드를 찾는 경우
      • 단, 간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 도드의 수, 즉 정점 차수만큼의 시간이 필요
    2. 인접 행렬
      • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우
      • 두 정점을 연결하는 간선의 존재여부(M[i][j])를 O(1)안에 즉시 알 수 있다.
      • 정점의 차수는 O(N)안에 알 수 있다. (인접 배열의 i번 째 행 또는 열을 모두 더한다.)
      • 단, 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야한다.
      • 그래프에 존재하는 모든 간선의 수는 O(n^2) 안에 알 수 있다. (인접 행렬 전체를 검색)

코드 설계

  1. 루트에서 시작한다.
  2. 자식 노드들을 [1]에 저장한다.
  3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
  4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
  5. 위의 과정을 반복한다.
  6. 모든 노드를 방문하면 탐색을 마친다.

코드 구현

  • 행렬로 구현한 그래프 (인접행렬)
public class Graph {
    private int[][] MATRIX; // 그래프 배열 선언

    public Graph() {}

    public Graph(int initSize) {
        this.MATRIX = new int[initSize + 1][initSize + 1];
    }

    public void put(int x, int y) {
        MATRIX[x][y] = MATRIX[y][x] = 1;
    }

    public void printGraph() {
        for (int i = 0; i < MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[i].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
    }
}
  • 리스트로 구현한 그래프 (인접 리스트)
public class Graph {
    private int V;
    private LinkedList<Integer>[] adjacent;

    public Graph(int V) {
        this.V = V;
        this.adjacent = new LinkedList[V];
        for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
    }

    public void addEdge(Graph graph, int src, int dest) {
        graph.adjacent[src].add(dest);
        graph.adjacent[dest].add(src);
    }

    public void printGraph(Graph graph) {
        for (int v = 0; v < graph.V; v++) {
            System.out.println("Adjacency list of vertex " + v);
            System.out.print("head");
            for (Integer pCrawl : graph.adjacent[v]) {
                System.out.print(" -> " + pCrawl);
            }
            System.out.println("\n");
        }
    }
}

+ Recent posts