codejcd 기술 블로그

문제

https://www.acmicpc.net/problem/4963

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

기존 상하좌우만 탐색하는 케이스와 달리 대각선까지 탐색하기 때문에 이를 탐색하기 위한 값들을 잘 정의해줘야합니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에  탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

https://www.acmicpc.net/problem/4963

문제

https://www.acmicpc.net/problem/11724

분석/설계

그래프를 탐색하는 DFS/BFS 유형의 문제입니다.

구현 시 주의할 점은 방문을 체크하는 배열을 크기를 +1 해줘야 합니다.

그렇지 않을 경우 조건에서 N이 1부터 시작하기 때문에 마지막 수를 체크할 때  

Array 크기를 초과하여 Exception이 발생하게 됩니다.

구현 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N; // 정점 개수
	static int M; // 간선 개수
	static boolean[] visited; // 방문한 곳
	static ArrayList<ArrayList<Integer>> map = new ArrayList<>(); // 그래프
	static int cnt; // 연결 요소의 개수 
	
	public static void dfs(int v) {
		visited[v] = true;
		
		for (int i=0; i<map.get(v).size(); i++) {
			int w = map.get(v).get(i);
			if (!visited[w]) dfs(w);
		}
	}
	
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v);

		visited[v] = true;
		
		while(!queue.isEmpty()) {
			int x= queue.poll();
		
			for (int i=0; i<map.get(v).size(); i++) {
				int w = map.get(x).get(i);
				if(!visited[w]) {
					queue.offer(w);
					visited[w] = true;
				}	
			}
			
		}
		
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		N = scanner.nextInt();
		M = scanner.nextInt();
		
		for(int i=0; i<=N; i++) {
			map.add(new ArrayList<>());
		}
		
		visited = new boolean[N+1];
		
		for (int i=0; i<M; i++) {
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			map.get(v1).add(v2);
			map.get(v2).add(v1);
		}
		
		for(int i=1; i<=N; i++) {
			if(!visited[i]) {
				dfs(i);
				cnt++;
			}
		}	
		System.out.println(cnt);
		scanner.close();
	}
}

정리

간단하지만 조건을 정확하게 확인해야 실수를 줄일 수 있습니다.

참고

https://www.acmicpc.net/problem/11724

문제

https://www.acmicpc.net/problem/1012

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에 상하좌우 탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 상하좌우를 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

https://www.acmicpc.net/problem/1012

ZoneId

시간대.  java.time.ZoneId 클래스에 대해 알아보겠습니다.

지역 ID는 {지역}/{도시}로 구성됩니다. 

다음 주소에서 각 정보들을 확인 가능합니다. (https://www.iana.or/time-zones)

ZoneDateTime

지정한 시간대에 상대적인 시점으로 LocalDateTime과 ZoneId가 합쳐진 개념이라고 보면 됩니다.

ZoneOffset

런던 그리니치 0도 자오선과 시간 값의 차이를 표현할 수 있는 기능들을 제공하는 클래스입니다.

예제를 통해서 사용 예시를 확인해보겠습니다.

import java.time.*;
import java.util.TimeZone;

public class Main {
	public static void main(String[] args) {
		ZoneId romeZone = ZoneId.of("Europe/Rome");
		ZoneId seoulZone = ZoneId.of("Asia/Seoul");
		
		ZoneId zoneId = TimeZone.getDefault().toZoneId();
		
		ZonedDateTime zdt1 = date.atStartOfDay(seoulZone);
		LocalDateTime dateTime = LocalDateTime.of(2022, Month.DECEMBER, 22, 23, 45);
		ZonedDateTime zdt2 = dateTime.atZone(seoulZone);
		Instant instant = Instant.now();
		ZonedDateTime zdt3 = instant.atZone(seoulZone);
		
		System.out.println(zdt1);
		System.out.println(zdt2);
		System.out.println(zdt3);

		ZoneOffset newYork = ZoneOffset.of("-05:00");
		OffsetDateTime daOffsetDateTime = OffsetDateTime.of(dateTime, newYork);
		System.out.println(daOffsetDateTime);
    }
}

출력 값

2022-10-22T00:00+09:00[Asia/Seoul]
2022-12-22T23:45+09:00[Asia/Seoul]
2022-11-28T20:54:25.808109400+09:00[Asia/Seoul]
2022-12-22T23:45-05:00

※ UTC = 협정 세계시, GMT(그리니치 표준시)

TemporalAdjusters는 복잡한 날짜 조정 기능에 사용하는 기능을 제공하는 클래스입니다.

다음 예제를 통해 사용 예시를 알아보겠습니다.

import java.time.*;
import java.time.temporal.ChronoUnit;
import static java.time.temporal.TemporalAdjusters.*;

public class Main {
	public static void main(String[] args) {
    	LocalDate date1 = LocalDate.of(2022, 11, 21);
		LocalDate date2 = date1.with(nextOrSame(DayOfWeek.SUNDAY));
		LocalDate date3 = date1.with(lastDayOfMonth());
		LocalDate date4 = date1.with(firstDayOfNextMonth());
		
		System.out.println(date1);
		System.out.println(date2);
		System.out.println(date3);
		System.out.println(date4);
    }
}

출력 값

2022-11-21
2022-11-27
2022-11-30
2022-12-01

TemporalAdjusters 클래스의 팩토리 메서드

DateTimeFormatter

포매팅과 파싱 전용 java.time.format 패키지 중 DateTimeFormatter 클래스입니다.

정적 팩토리 메서드와 상수를 이용해 쉽게 포매터를 만들 수 있습니다.

예제를 통해 사용 예시를 확인해보겠습니다.

import java.time.*;
import java.time.format.DateTimeFormatter;
import java.time.temporal.ChronoUnit;
import static java.time.temporal.TemporalAdjusters.*;

public class Main {
	public static void main(String[] args) {
		String s1 = date.format(DateTimeFormatter.BASIC_ISO_DATE);
		String s2 = date.format(DateTimeFormatter.ISO_LOCAL_DATE);
		LocalDate ld1 = LocalDate.parse("20221121", DateTimeFormatter.BASIC_ISO_DATE);
		LocalDate ld2 = LocalDate.parse("2022-11-21", DateTimeFormatter.ISO_LOCAL_DATE);
				
		System.out.println(s1);
		System.out.println(s2);
		
		System.out.println(ld1);
		System.out.println(ld2);
		
		DateTimeFormatter formatter = DateTimeFormatter.ofPattern("HH:mm:ss");
		LocalTime colonTime = LocalTime.of(17, 59, 59);
		
		System.out.println(formatter.format(colonTime));
    }
}

출력 값

20221022
2022-10-22
2022-11-21
2022-11-21
17:59:59

Instant 

Instant 클래스는 앞에서 봤던 LocalDate, LocalTime, LocalDateTime 과 달리

기계 관점에서 날짜와 시간을 표현하기 위해 사용합니다.

기계 관점에서는 사람과 달리 날짜와 시간을 구분하기 보다는 하나의 수를 사용하는 것이

계산에 용이하기 때문에 유닉스 에포크 시간(unix epoch time) 1970년 1월 1일 0시 0분 0초 UTC를 기준으로

특정 지점까지 시간을 초로 표현합니다.

팩토리 메서드 ofEpochSecond에 초를 넘겨서 클래스 인스턴스를 생성할수 있으며, 나노초의 정밀도를 제공합니다.

다음 예제를 통해 사용 예시를 확인해보겠습니다.

import java.time.*;

public class Main {
	public static void main(String[] args) {
 		Instant i3 = Instant.ofEpochSecond(3);
		Instant i4 = Instant.ofEpochSecond(3, 1_000_000_000);
		Instant i2 = Instant.ofEpochSecond(3, -1_000_000_000);
		
		System.out.println(i3);
		System.out.println(i4);
		System.out.println(i2);   
    }
}

출력 값

1970-01-01T00:00:03Z
1970-01-01T00:00:04Z
1970-01-01T00:00:02Z

Duration

두 시간의 객체 사이의 지속 시간을 만들고 표현할수 있습니다.

나노초, 초 단위로 출력이 가능하게 메서드를 제공합니다.

두 개의 LocalTime, LocalDateTime, Instant을 Duration으로 만들 수있습니다.

다음 예제를 통해서 확인해보겠습니다.

import java.time.*;
import java.time.temporal.ChronoUnit;

public class Main {
	public static void main(String[] args) {
		LocalTime t1 = LocalTime.of(15, 05, 10);
		LocalTime t2 = LocalTime.of(16, 05, 10);
		
		LocalDateTime dateTime1 = LocalDateTime.of(2022, 12, 1, 12, 00, 00);
		LocalDateTime dateTime2 = LocalDateTime.of(2022, 12, 2, 13, 00, 00);
		
		Duration duration1 = Duration.between(t1, t2);
		Duration duration2 = Duration.between(dateTime1, dateTime2);
		
		Duration fiveMin = Duration.ofMinutes(5);
		Duration sixMin = Duration.of(6, ChronoUnit.MINUTES);
		
		System.out.println(duration1.getSeconds());
		System.out.println(duration2.getSeconds());
		System.out.println(fiveMin);
		System.out.println(sixMin);
    }
}

출력 값

3600
90000
PT5M
PT6M

Period

두 시간의 객체 사이의 지속 시간을 만들고 표현할수 있습니다.

년/월/일 단위로 나타냅니다.

Duration의 경우 최대 제어 가능한 단위는 "일" 입니다.

다음 예제를 통해 사용 예시를 확인해보겠습니다.

import java.time.*;
import java.time.temporal.ChronoUnit;

public class Main {
	public static void main(String[] args) {
		Period fourDays = Period.ofDays(4);
		Period TwoWeeks = Period.ofWeeks(2);
		Period oneYearTwoMonthsThreeDays = Period.of(1, 2, 3);
		
		System.out.println(fourDays.get(ChronoUnit.DAYS));
		System.out.println(TwoWeeks.get(ChronoUnit.DAYS));
		System.out.println(oneYearTwoMonthsThreeDays.get(ChronoUnit.YEARS));
		System.out.println(oneYearTwoMonthsThreeDays.get(ChronoUnit.MONTHS));
		System.out.println(oneYearTwoMonthsThreeDays.get(ChronoUnit.DAYS));
		
		Period fiveDays = fourDays.plus(Period.ofDays(1));
		System.out.println(fiveDays.get(ChronoUnit.DAYS));
		
		Period threeDays = fourDays.minus(Period.ofDays(1));
		System.out.println(threeDays.get(ChronoUnit.DAYS));
    }
}

출력 값

4
14
1
2
3
5
3

Duration과 Period 공통 제공 메서드

ChronoUnit

표준 날짜 기간 단위 집합.

이 단위 세트는 날짜, 시간 또는 날짜-시간을 조작하기위한 단위 기반 액세스를 제공합니다.