BangBang's Devlogs

www.acmicpc.net/problem/1181

문제

해결 방안

1. HashSet을 이용하여 입력을 받아 중복된 경우를 제거해준다.

2. ArrayList에 담아서 해당 ArrayList를 Collections.sort()를 이용하여 정렬해준다.
이 때, new Comparator를 사용하여 길이가 짧은 것과 길이가 같으면 사전순으로 정렬하는 코드를 구현해준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int n = Integer.parseInt(str);
		
		HashSet<String> set = new HashSet<>();
		
		for(int i=0; i<n; i++) {
			set.add(br.readLine());
		}
		
		List<String> words = new ArrayList<>(set);
		
		Collections.sort(words, new Comparator<String>() {
			@Override
			public int compare(String s1, String s2) {
				if(s1.length() < s2.length())
					return -1;
				else if(s1.length() > s2.length())
					return 1;
				else
					return s1.compareTo(s2);
			}
		});
		
		for(String word : words) {
			System.out.println(word);
		}
	}

}

www.acmicpc.net/problem/7568

문제

해결 방안

전체 경우의 수를 비교해보면 되는 간단한 문제이다. 완전탐색을 이용하여 peoples i번째의 키와 몸무게를 다른 j번째 키와 몸무게를 비교하면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 덩치
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int n = Integer.parseInt(str);
		
		int[][] peoples = new int[n][2];
		
		for(int i=0; i<n; i++) {
			str = br.readLine();
			peoples[i][0] = Integer.parseInt(str.split(" ")[0]);
			peoples[i][1] = Integer.parseInt(str.split(" ")[1]);
		}
		// 입력끝 ====
		
		int x1, y1;
		int x2, y2;
		int k;
		for(int i=0; i<n; i++) {
			x1 = peoples[i][0];
			y1 = peoples[i][1];
			k = 1;
			
			for(int j=0; j<n; j++) {
				if(i!=j) {
					x2 = peoples[j][0];
					y2 = peoples[j][1];
					
					if(x1<x2 && y1<y2) {
						k++;
					}
				}
			}
			System.out.print(k + " ");
		}
		
	}

}

www.acmicpc.net/problem/2667

문제

해결 방안

total이 단지 수가 되고 지도를 탐색하면서 1을 발견하면 total++을 해준다.
그리고 DFS탐색으로 통해 해당 단지에 속한 집의 갯수를 cnt에 저장하여 dfs()를 빠져나오면 ArrayList에 해당 cnt를 넣어준다.

그리고 ArrayList에 저장된 각 단지의 집의 갯수들을 정렬하여 출력해주면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int n;// 지도 크기
	static int[][] maps;
	static boolean[][] visited;
	
	static int total=0; // 총 단지수
	static int cnt;
	static List<Integer> cnts = new ArrayList<>();// 각 단지에 속하는 집의 수
	
	// 북 동 남 서
	static int[] dy = {-1, 0, 1, 0}; // 세로
	static int[] dx = {0, 1, 0, -1}; // 가로

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		n = Integer.parseInt(str);
		
		maps = new int[n][n];
		visited = new boolean[n][n];
		
		for(int i=0; i<n; i++) {
			str = br.readLine();
			for(int j=0; j<n; j++) {
				maps[i][j]=Integer.parseInt(str.split("")[j]);
			}
		}
		// === 입력 끝=======
		
		// 탐색 + 단지 수 정해주기
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				cnt = 0;
				if(maps[i][j]==1 && !visited[i][j]) {
					total++;
					cnt++;
					dfs(i, j);
					cnts.add(cnt);
				}
			}
		}
		
		// 출력
		System.out.println(total);
		Collections.sort(cnts);
		for(int i=0; i<cnts.size(); i++) {
			System.out.println(cnts.get(i));
		}
		
	}
	
	static void dfs(int cy, int cx) {
		
		visited[cy][cx] = true;
		
		int ny, nx;
		for(int i=0; i<4; i++) {
			ny = cy + dy[i];
			nx = cx + dx[i];
			
			if(ny>=0 && ny<n && nx>=0 && nx<n) {
				if(!visited[ny][nx] && maps[ny][nx]==1) {
					cnt++;
					dfs(ny, nx);
				}
			}
		}
		
	}

}

www.acmicpc.net/problem/1012

문제

해결 방안

배추가 있는 공간들을 DFS 탐색을 통해 분리된 갯수를 찾는 문제이다.

maps에 배추가 있는 값들을 추가해주고 maps를 탐색하면서 1(배추가 있는 곳)일 때 result(지렁이)++해주고 DFS를 해서 visited를 true로 만들어줘서 다음에 1일때 이미 방문했으면 넘어갈 수 있게 해주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//유기농 배추
public class Main {
	
	static int m; // 가로길이(1~50)
	static int n; // 세로길이(1~50)
	static int k; // 배추가 심어져있는 위치의 갯수(1~2500)
	static int[][] maps; // 배추 지도
	static boolean[][] visited;
	static int result; // 최소 벌레 수
	
	// 북 동 남 서
	static int[] dx = {0, 1, 0, -1}; // 가로
	static int[] dy = {-1, 0, 1, 0}; // 세로

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int t = Integer.parseInt(str);
		
		for(int i=0; i<t; i++) {
			str = br.readLine();
			m = Integer.parseInt(str.split(" ")[0]);
			n = Integer.parseInt(str.split(" ")[1]);
			k = Integer.parseInt(str.split(" ")[2]);
			
			maps = new int[n][m];
			visited = new boolean[n][m];
			result = 0;
			
			// 배추 심어져있는 갯수
			int x; // 가로
			int y; // 세로
			for(int j=0; j<k; j++) {
				str = br.readLine();
				x = Integer.parseInt(str.split(" ")[0]);
				y = Integer.parseInt(str.split(" ")[1]);
				// 지도에 넣어주기
				maps[y][x] = 1;
			}
			
			// 지렁이 둘 구간 탐색
			for(int a=0; a<n; a++) {
				for(int b=0; b<m; b++) {
					//System.out.print(maps[a][b]);
					if(maps[a][b]==1 && !visited[a][b]) {
						result++;
						visited[a][b] = true;
						dfs(a, b);
					}
				}
			}
			//결과값 출력
			System.out.println(result);
		}
	}
	
	static void dfs(int y, int x) {
		int nx, ny;
		
		for(int i=0; i<4; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			
			// 범위 체크
			if(ny>=0 && nx>=0 && ny<n && nx<m) {
				// 배추가 있고 방문 안한 곳
				if(maps[ny][nx]==1 && !visited[ny][nx]) {
					visited[ny][nx] = true;
					dfs(ny, nx);
				}				
			}
		}
	}

}

www.acmicpc.net/problem/2178

문제

미로의 (1,1) 에서 (n,m)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

BFS + DP를 이용하여 해결하였다.

해결 방안

1. 미로의 이동 가능 여부 관련 값은 maps[][]에 저장하였다.(1이면 이동 가능)
미로의 해당 칸으로 이동할 때 지나야하는 최소의 칸 수는 cnts[][]에 저장하였다.(0이면 한번도 이동 안한 곳)

2. 주어진 maps의 (1,1) 위치에서 (m,n)으로 BFS 방법으로 4방향을 탐색하고 DP를 이용하여 cnts에 지나야하는 최소 칸 수를 메모제이션하였다.

3. cnts[n][m]을 출력하면 도착 위치에 가기위해 지나야하는 최소의 칸을 출력한다.

코드

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 m; // 가로
	static int[][] maps;
	static int[][] cnts; // 이동할 때 최소 칸수
	
	// 북 동 남 서
	static int[] dy = {-1, 0, 1, 0}; // 세로
	static int[] dx = {0, 1, 0, -1}; // 가로
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		
		maps = new int[n+1][m+1];
		cnts = new int[n+1][m+1];
		
		StringTokenizer st;
		for(int i=1; i<n+1; i++) {
			str = br.readLine();
			
			for(int j=1; j<m+1; j++) {
				maps[i][j] = Integer.parseInt(str.split("")[j-1]);
			}
		}
		
		// == 입력 끝
		
		bfs();

		// 도착위치(n,m) 의 최소 칸 수 
		System.out.println(cnts[n][m]);
	}
	
	static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		
		// 1,1에서 시작
		q.offer(new int[]{1,1});
		cnts[1][1] = 1;
		
		// 세로, 가로
		int[] current = new int[2];
		int[] next = new int[2];
		while(!q.isEmpty()) {
			current = q.poll();
			
			// 4방향의 인접 위치
			for(int i=0; i<4; i++) {
				next[0] = current[0] + dy[i];
				next[1] = current[1] + dx[i];
				
				// 범위 안에 있고 이동할 수 있는 곳이고(map[][]==1) 방문한 적 없을 때(cnts[][]==0)
				if(next[0]>0 && next[1]>0 && next[0]<=n && next[1]<=m && maps[next[0]][next[1]]==1 && cnts[next[0]][next[1]]==0) {
					q.offer(new int[] {next[0], next[1]});
					cnts[next[0]][next[1]] = cnts[current[0]][current[1]]+1;
				}
			}
		}
	}

}

www.acmicpc.net/problem/2606

문제

입력의 첫째 줄이 그래프의 노드 갯수가 되고 둘째 줄이 간선의 갯수가 될 것이다.
또한 무방향 그래프가 될것이다. 

해결 방안

무방향 그래프를 ArrayList를 이용하여 구현하였다.

1번부터 시작하는 DFS 탐색을 하였으며 DFS의 depth를 바이러스 감염 시킨 컴퓨터 갯수로 하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

// 바이러스
public class Main {
	
	static int n; // v
	static int e; // edge
	static ArrayList<ArrayList<Integer>> graph;
	static boolean[] visited;
	static int cnt; // 결과

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		e = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		visited = new boolean[n+1];
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		String str;
		int v1, v2;
		for(int i=0; i<e; i++) {
			str = br.readLine();
			v1 = Integer.parseInt(str.split(" ")[0]);
			v2 = Integer.parseInt(str.split(" ")[1]);
			
			graph.get(v1).add(v2);
			graph.get(v2).add(v1);
		}
		
		// ==== 입력 끝
		cnt = 0;
		dfs(1);
		
		System.out.println(cnt);
	}
	
	static void dfs(int start) {
		
		visited[start] = true;
		
		int y;
		for(int i=0; i<graph.get(start).size(); i++) {
			y = graph.get(start).get(i);
			
			if(!visited[y]) {
				visited[y] = true;
				cnt++;
				dfs(y);
			}
		}
	}

}

www.acmicpc.net/problem/10974

문제

해결 방안

모든 순열을 출력하는 기본적인 DFS 문제이다.

DFS + 백트래킹을 이용하여 구현하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 모든 순열
public class Main {

	static int n;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		visited = new boolean[n+1];
		
		String sNum;
		for(int i=1; i<=n; i++) {
			visited[i] = true;
			sNum = Integer.toString(i);
			//System.out.println("sNum: " + sNum);
			dfs(sNum, i, 1);
			visited[i] = false;
		}
	}
	
	static void dfs(String sNum, int start, int depth) {
		if(depth>=n) {
			System.out.println(sNum);
		}
		else {
			for(int i=1; i<=n; i++) {
				if(!visited[i]) {
					visited[i] = true;
					sNum += " "+i;
					dfs(sNum, start, depth+1);
					sNum = sNum.substring(0, sNum.length()-2);
					visited[i] = false;
				}
			}
		}
	}

}

www.acmicpc.net/problem/1697

문제

해결 방안

time 배열의 index는 해당 위치이고 값은 해당 위치를 수빈이가 최소 몇 초를 나타낸다.
또한 수빈이는 3가지 방법으로 이동할 수 있으므로 3가지 방법으로 이동한 위치의 값이 k 일때까지 너비우선 탐색을 해주면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

// 숨바꼭질
// 수빈이 N 동생 K
// 수빈이는 걷거나 순간이동 가능
public class Main {

	static int n;
	static int k;
	static int[] time;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		n = Integer.parseInt(str.split(" ")[0]);
		k = Integer.parseInt(str.split(" ")[1]);

		time = new int[100001];
		
		if(n==k)
			System.out.println(0);
		else
			bfs();
	}
	
	static void bfs() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(n);
		
		int current = 0;
		
		int next = 0;
		while(!q.isEmpty()) {
			current = q.poll();

			for(int i=0; i<3; i++) {
				if(i==0) {
					next = current+1;
				}
				else if(i==1) {
					next = current-1;
				}
				else {
					next = 2*current;
				}
				
				if(next == k) {
					System.out.println(time[current]+1);
					return;
				}
				
				if(next>=0 && next<=100000 && time[next]==0) {
					q.offer(next);
					time[next] = time[current]+1;
				}
				
			}
		}
	}

}