사전 캠프 11일차

오늘은 코딩 테스트 그래프 이론 부분 마무리를 지을 생각이다!

 

2468번 안전 영역

 

문제를 풀기전 : 안전한 영역이 만들어지는지 bfs를 사용하자 100까지니까 인접 행렬 사용해도 충분하다. bfs에 들어 갈 때마다 count 값을 늘려주고 max 값과 비교해서 max값을 출력하자

 

class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static boolean visited[][];
	public static int parent[];
	public static int n;
	public static int m;
	public static int h;
	public static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		n = Integer.parseInt(bf.readLine());
		arr = new int[n][n];
		int highMax = 0;
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for(int j=0;j<n;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] > highMax) {
					highMax = arr[i][j];
				}
			}
		}
		int max = 1;
		for(int i=1;i<highMax;i++) {
			visited = new boolean[n][n];
			count = 0;
			for(int j=0;j<n;j++) {
				for(int k=0;k<n;k++) {
					if(arr[j][k] > i && !visited[j][k]) {
						count++;
						bfs(j,k,i);
					}
				}
			}
			if(count > max) {
				max = count;
			}
		}
		System.out.println(max);
	}
	public static void bfs(int x, int y, int dep) {
		int [] xflag = {-1,0,0,1};
		int [] yflag = {0,-1,1,0};
		Queue <Node> q = new LinkedList<>();
		visited[x][y] = true;
		q.add(new Node(x,y));
		while(!q.isEmpty()) {
			Node no = q.poll();
			x = no.x;
			y = no.y;
			for(int i=0;i<4;i++) {
				int newX = x + xflag[i];
				int newY = y + yflag[i];
				if(newX >= 0 && newY >=0 && newX <n && newY <n) {
					if(arr[newX][newY] > dep && !visited[newX][newY]) {
						q.add(new Node(newX,newY));
						visited[newX][newY] = true;
					}
				}
			}
		}
		
	}
}

 

전형적인 쉬운 문제지만 max 값을 0이 아닌 1로 두어야한다 비가 안올 수 도 있기 때문에! 그리고 BFS보다 DFS가 성능이 더 좋다... DFS가 대부분 메모리 효율성이 높기 때문에 최단 경로 문제가 아닌이상 DFS를 선택하자!

 

 

4963번 섬의 개수

섬의 개수를 세는 문제로 생각보다 간단할것으로 보인다. 위에서 본 것처럼 dfs로 사용하고 50보다 작으니 인접행렬을 사용하자 while(true)로 무한 루프를 돌리고  0 0을 받았을 때 나가자

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static boolean visited[][];
	public static int parent[];
	public static int n;
	public static int w;
	public static int h;
	public static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		while(true) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			if(w==0 && h==0) {
				break;
			}
			arr = new int[h][w];
			visited = new boolean[h][w];
			for(int i=0;i<h;i++) {
				st = new StringTokenizer(bf.readLine());
				for(int j=0;j<w;j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			count = 0;
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					if(arr[i][j]==1 && !visited[i][j]) {
						count++;
						visited[i][j] = true;
						dfs(i,j);
					}
				}
			}
			System.out.println(count);
		}
		
	}
	public static void dfs(int x, int y) {
		int [] xflag = {-1,-1,-1,0,0,0,1,1,1};
		int [] yflag = {-1,0,1,-1,0,1,-1,0,1};
		for(int i=0;i<9;i++) {
			int newX = x + xflag[i];
			int newY = y + yflag[i];
			if(newX >= 0 && newY >=0 && newX <h && newY <w) {
				if(arr[newX][newY] == 1 && !visited[newX][newY]) {
					visited[newX][newY] = true;
					dfs(newX,newY);
				}
			}
		}	
	}
}

 

문제를 꼼꼼하게 읽자! 대각선도 붙어있다고 처리가 되니 주변 9개 모두 탐색을 해야한다! 그외엔 다른 점이 없었다.

 

7562번 나이트의 이동

 

이번엔 나이트의 이동이다 이동할 수 있는 위치는 총 8 군데이며 최소한의 이동으로 원하는 위치에 도착해야 하므로최단 경로 문제로 BFS 이고 arr 값에 전 arr 값 + 1 을 한 값을 넣으면서 이동하면 될 듯하다!

class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static boolean visited[][];
	public static int tx;
	public static int ty;
	public static int l;
	public static int count;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		int tcase = Integer.parseInt(bf.readLine());
		for(int i=0;i<tcase;i++) {
			l = Integer.parseInt(bf.readLine());
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int nx = Integer.parseInt(st.nextToken());
			int ny = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(bf.readLine());
			tx = Integer.parseInt(st.nextToken());
			ty = Integer.parseInt(st.nextToken());
			arr = new int[l][l];
			visited = new boolean[l][l];
			bfs(nx,ny);
		}
		
	}
	public static void bfs(int x, int y) {
		Queue <Node> q = new LinkedList<>();
		int [] dx = {-2,-1,1,2,2,1,-1,-2}; 
		int [] dy = {-1,-2,-2,-1,1,2,2,1};
		q.add(new Node(x,y));
		while(!q.isEmpty()) {
			Node n = q.poll();
			x = n.x;
			y = n.y;
			if(x==tx && y==ty) {
				System.out.println(arr[x][y]);
				return;
			}
			for(int i=0;i<8;i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if(newX >= 0 && newY >=0 && newX <l && newY <l) {
					if(arr[newX][newY] == 0) {
						arr[newX][newY] = arr[x][y] + 1;
						q.add(new Node(newX,newY));
					}
				}
			}	
		}

	}
}

 

예상대로 쉽게 풀렸다! 이제 쉬운 DFS / BFS 문제는 거의 풀이 안보고 쉽게 푸는 듯하다!

 

2583번 영역 구하기

 

영역의 개수니까 dfs를 쓰려고 했는데 bfs를 써야 갯수를 세는데 더 유리할거 같다. 

 

class Node{
	int x;
	int y;
	public Node(int y, int x) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int [][] arr;
	public static boolean visited[][];
	public static int m;
	public static int n;
	public static int k;
	public static int count;
	public static ArrayList<Integer> result;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		arr = new int[m][n];
		visited = new boolean[m][n];
		result = new ArrayList<>();
		for(int i=0;i<k;i++) {
			st = new StringTokenizer(bf.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			for(int j=y1;j<y2;j++) {
				for(int l=x1;l<x2;l++) {
					arr[j][l]=1;
				}
			}
		}
		for(int i=0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(!visited[i][j] && arr[i][j]==0)
					bfs(i,j);
			}
		}
		System.out.println(result.size());
		Collections.sort(result);
		for(int a : result) {
			sb.append(a+" ");
		}
		System.out.println(sb);
	}
	public static void bfs(int y, int x) {
		Queue <Node> q = new LinkedList<>();
		int [] dx = {-1,0,0,1}; 
		int [] dy = {0,-1,1,0};
		q.add(new Node(y,x));
		count = 1;
		visited[y][x] = true;
		while(!q.isEmpty()) {
			Node no = q.poll();
			y = no.y;	
			x = no.x;
			for(int i=0;i<4;i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if(newX >= 0 && newY >=0 && newX < n && newY <m) {
					if(arr[newY][newX] == 0 && !visited[newY][newX]) {
						count++;
						visited[newY][newX] = true;
						q.add(new Node(newY,newX));
					}
				}
			}	
		}
		result.add(count);

	}
}

매번 주먹구구식으로 x,y좌표를 주다가 이번에 신경썼더니 내가 만들고 내가 헷갈려서 실수를 많이했다 앞으로는 조금 더 신경 써서 x와 y를 구분하자

 

1987번 알파벳

범위가 20까지? 생각보다 적다 행렬을 써도 되겠다. 최대한 많은 칸을 가야하기 때문에 dfs + 백트래킹이 아닐까 생각한다. 26칸 짜리 배열을 하나 만들어서 알파벳이 사용 되었는지 확인해야 할거같다!

 

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static char [][] arr;
	public static boolean checked[];
	public static int r;
	public static int c;
	public static int max_len = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		arr = new char[r][c];
		checked = new boolean[26];
		for(int i=0;i<r;i++) {
			String[] tokens = bf.readLine().split("(?<=[A-Z])");
			int count = 0;
			for(String token : tokens) {
				arr[i][count++] = token.charAt(0);
			}
		}
		dfs(0,0,1);

		System.out.println(max_len);
	}
	public static void dfs(int y, int x, int len) {
		int [] dx = {-1,0,0,1}; 
		int [] dy = {0,-1,1,0};
		checked[arr[y][x]-65] = true; 
		max_len = Math.max(max_len, len);
		for(int i=0;i<4;i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			if(newX >= 0 && newY >=0 && newX < c && newY <r) {
				if(!checked[arr[newY][newX]-65]) {
					dfs(newY,newX, len+1);
				}
			}
		}
		checked[arr[y][x]-65] = false; 
	}
}

 

백트래킹 문제는 아직 확실히 약하다 for문 안에서 백트래킹했다가 망했다. 나머지는 그래도 풀만했던거 같다!