[코드트리 조별과제] 2주차 - BFS / DP 학습

JYC·2024년 7월 27일
코드트리코딩테스트코딩트리조별과제

[코드트리 조별과제]

목록 보기
1/5
post-thumbnail

2주차에는 INTERMEDIATE LOW 부분 중 BFS와 DP I에 대해 학습했다.

BFS - 네 방향 탈출 가능 여부 판별하기

유형문제 경험치난이도
Intermediate Low / BFS / BFS 탐색40xp난이도

[문제링크]에서 문제를 참고하자.

방문 여부 확인용 배열 , 동서남북 이동 배열과 BFS를 위한 Queue를 필요로 하는 문제이다.

Queue에 시작 위치를 저장하고, 각각의 동서남북으로 이동해 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;//배열 크기
	static int[][] map; //배열
	static boolean[][] visited; //방문여부 확인
	static int[] dy = {1,-1,0,0}; //동서남북 이동
	static int[] dx = {0,0,1,-1}; //동서남북 이동
	static Queue<int[]> queue = new LinkedList<>(); //bfs용
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n+1][m+1];
		visited = new boolean[n+1][m+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=m; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		if(bfs()) { //만약 오측 하단까지 도달했다면
			System.out.println(1);
		}
		else { //도달하지 못한 경우
			System.out.println(0);
		}	
	}
	
	public static boolean bfs() {
		visited[1][1]=true;
		queue.add(new int[] {1,1}); //초기 시작 위치 저장
		
		while(!queue.isEmpty()) {
			int[] temp = queue.poll();
			int tx = temp[0];
			int ty = temp[1];
			
			for(int i=0; i<4; i++) { //동서남북 탐색
				int nx = tx+dx[i];
				int ny = ty+dy[i];
				
				if(nx>n||nx<1||ny>m||ny<1) { //범위 벗어나면 X
					continue;
				}
				if(visited[nx][ny] || map[nx][ny]!=1) { //이미 방문했거나 1이 아니라면 X
					continue;
				}
				
				if(nx==n && ny==m) { //우측 하단에 도달한 경우
					return true;
				}
				queue.add(new int[] {nx,ny}); //동서남북 새로운 위치 저장
				visited[nx][ny]=true;
			}
		}
		return false; //우측 하단 도달하지 못한 경우
	}

}

BFS - 갈 수 있는 곳들

유형문제 경험치난이도
Intermediate Low / BFS / BFS 탐색40xp난이도

[문제링크]에서 문제를 참고하자.

위에서 봤던 네 방향 탈출 가능 여부 판별하기 와 비슷한 문제이다.

동서남북 배열, 방문 여부 확인용 배열 등 비슷한 부분이 많지만 이 문제는 갈 수 있는 구역을 체크해 출력하는 문제로 BFS로 동서남북 체크하면서 갈 수 있는 구역을 하나씩 늘려가며 최종적으로 최대한 갈 수 있는 구역을 출력하면 된다.

이를 위해 static 변수로 ans라는 int형 변수를 설정하고 구역을 찾을 때마다 ++해주는 방식을 사용했다.

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;//배열 크기
	static int k; //시작 지점
	static int[][] map; //배열
	static boolean[][] visited; //방문여부 확인
	static int[] dy = {1,-1,0,0}; //동서남북 이동
	static int[] dx = {0,0,1,-1}; //동서남북 이동
	static Queue<int[]> queue = new LinkedList<>(); //bfs용
	static int ans=0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new int[n+1][n+1];
		visited = new boolean[n+1][n+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			if(!visited[x][y]) {
				ans++;
				bfs(x,y);
			}
		}
		System.out.println(ans);
	}
	
	public static void bfs(int x,int y) {
		visited[x][y]=true;
		queue.add(new int[] {x,y}); //초기 시작 위치 저장
		
		while(!queue.isEmpty()) {
			int[] temp = queue.poll();
			int tx = temp[0];
			int ty = temp[1];
			
			for(int i=0; i<4; i++) { //동서남북 탐색
				int nx = tx+dx[i];
				int ny = ty+dy[i];
				
				if(nx>n||nx<1||ny>n||ny<1) { //범위 벗어나면 X
					continue;
				}
				if(visited[nx][ny] || map[nx][ny]!=0) { //이미 방문했거나 0이 아니라면 X
					continue;
				}
				
				ans++;
				queue.add(new int[] {nx,ny}); //동서남북 새로운 위치 저장
				visited[nx][ny]=true;
			}
		}
	}

}

DP - 최대 증가 부분 수열

유형문제 경험치난이도
Intermediate Low / DP I / 조건에 맞게 선택적으로 전진하는 DP40xp난이도

[문제링크]에서 문제를 확인하자.

DP용 배열 하나를 설정하고 , 입력 받은 숫자 배열에서 각각의 값을 비교해 인덱스가 더 큰 배열의 값이 더 크다면 dp[i] = Math.max(dp[i], dp[j]+1); 로 최대 값을 찾아나간다.

마지막으로 DP 배열을 sort해주고,dp 배열의 최댓값을 가장 끝으로 보낸 후 dp 배열의 가장 마지막 인덱스 값을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		dp = new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		dp[0]=1;
		
		for(int i=1; i<n; i++) {
			dp[i]=1;
			for(int j=0; j<i; j++) {
				if(arr[j]<arr[i]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
		}
		Arrays.sort(dp);
		System.out.println(dp[n-1]);
	}

}

DP - 최대 감소 부분 수열

유형문제 경험치난이도
Intermediate Low / DP I / 조건에 맞게 선택적으로 전진하는 DP60xp난이도

[문제링크]에서 문제를 확인하자.

위 문제와 비슷하지만 이 문제는 반대로 배열이 감소하는 형태로 최댓값을 찾아나가야 하는 방식이다. 고로, 배열 비교 부분을 바꿔주기만 하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		dp = new int[n];
		
		st=new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0]=1;
		
		for(int i=1; i<n; i++) {
			dp[i]=1;
			for(int j=0; j<i; j++) {
				if(arr[i]<arr[j]) { //더 작은 경우
					dp[i]=Math.max(dp[i], dp[j]+1);
				}
			}
		}
		Arrays.sort(dp);
		System.out.println(dp[n-1]);
	}
}
profile
JYC
열심히 하기 1일차
다음 포스트

[코드트리 조별과제] 3주차 - DP / 백트래킹 학습

0개의 댓글