학습일지/삼성 SDS 알고리즘 특강
삼성 SDS 대학생 알고리즘 특강 1일차 - DFS&BFS
이재빵
2022. 7. 18. 22:39
728x90
항상 구현 전에 주석처리하고 시작 할 것.
DFS와 BFS를 구분 짓는 가장 중요한 점 "동시성"
동시에 무언가를 해야한다? BFS!
DFS
방문'한'게 스택에 들어감
1.체크인(방문)
2.목적지인가?
3.연결된 곳을 순회
4.갈 수 있는가?
5.간다.
6.체크아웃
항상 1,6의 뎁스 맞추는 것을 명심해야 한다. 그래야 스택오버플로우 실수를 예방할 수 있음.
BFS
방문'할'게 큐에 들어감
1.큐에서 꺼내옴
2.목적지인가?
3.연결된 곳을 순회
4.갈 수 있는가?
5.체크인
6.큐에 넣음.
1062번: 가르침
import java.util.Scanner;
public class Main {
static int N, K;
static String[] words;
static boolean[] visited = new boolean[26];
static int selectedCount = 0;
static int max = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
words = new String[N];
visited['a' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;
visited['i' - 'a'] = true;
visited['c' - 'a'] = true;
if(K == 26){
System.out.println(N);
} else if(K<5){
System.out.println(0);
} else {
for (int i = 0; i < N; i++) {
String str = sc.next();
//words[i] = str.substring(4,str.length()-4);
words[i] = str.replaceAll("[antic]", "");
}
selectedCount = 5;
max = countWords();
for (int i = 0; i < 26; i++) {
if (visited[i] == false) {
dfs(i);
}
}
System.out.println(max);
}
}
static void dfs(int index){
// 1.체크인(방문)
visited[index] = true;
selectedCount++;
// 2.목적지인가?: selectedCount == K => 읽을 수 있는 단어 개수 계산
if(selectedCount == K){
//계산
max = Math.max(max,countWords());
} else {
// 3.연결된 곳을 순회 : index + 1 ~ 25
for(int i=index+1; i<=25; i++){
// 4.갈 수 있는가? : 방문 여부
if(visited[i]==false){
// 5.간다. : dfs()
dfs(i);
}
}
}
// 6.체크아웃
visited[index] = false;
selectedCount--;
}
static int countWords(){
int count = 0;
for(int n=0; n<N; n++){
boolean isPossible = true;
String word = words[n];
for(int i=0; i<word.length(); i++){
if(visited[word.charAt(i) - 'a']==false) {
isPossible = false;
break;
}
}
if(isPossible){
count++;
}
}
return count;
}
}
1759번: 암호 만들기
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int L, C;
static char[] data;
static List<String> result;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
L = sc.nextInt();
C = sc.nextInt();
data = new char[C];
result = new LinkedList<>();
for (int i = 0; i < C; i++) {
data[i] = sc.next().charAt(0);
}
Arrays.sort(data);
dfs(0,0,0,-1,"");
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
static void dfs(int length, int ja, int mo, int current, String pwd){
// 1.체크인 - 생략 가능
// 2.목적지인가?: length == L => ja 개수, mo 개수 확인 암호 가능 판별
if(length == L){
if(ja>=2 && mo>=1){
result.add(pwd);
}
} else {
// 3.연결된 곳을 순회 : current +1 ~ C
for(int i= current +1; i<C; i++){
// 4.갈 수 있는가? : 정렬했기 때문에 다 갈 수 있음
// 5.간다 -> ja, mo
if(data[i]=='a' || data[i]=='e' || data[i]=='i' || data[i]=='o' || data[i]=='u'){
dfs(length+1, ja, mo+1, i, pwd+data[i]);
} else {
dfs(length+1, ja+1, mo, i, pwd+data[i]);
}
}
}
// 6.체크아웃 - 생략 가능
}
}
3055: 탈출
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Node {
int x;
int y;
int type;
public Node(int y, int x, int type){
this.y = y;
this.x = x;
this.type = type;
}
}
// 좌, 우, 위, 아래
static final int[] dx = {-1, 1, 0, 0};
static final int[] dy = {0, 0, -1, 1};
static int R, C;
static char[][] map;
static int[][] dp;
static Queue<Node> queue;
static boolean foundAnswer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
map = new char[R][C];
dp = new int[R][C];
queue = new LinkedList<>();
Node st = null;
for (int r = 0; r < R; r++) {
String str = sc.next();
for (int c = 0; c < C; c++) {
map[r][c] = str.charAt(c);
//물 먼저 넣음. 전제조건에서 다음 턴에 물이 번질 가능성이 있는 위치에는 고슴도치가 이동할 수 없기 때문에
//물이 먼저 범람하도록 하여 이를 쉽게 해결.
if (map[r][c] == '*') {
queue.add(new Node(r, c, '*'));
} else if (map[r][c] == 'S') {
st = new Node(r, c, 'S');
}
}
}
queue.add(st);
while (!queue.isEmpty()) {
// 1.큐에서 꺼내옴(큐에는 이동할 곳이 들어감) -> *, s, ., D
Node n = queue.poll();
// 2.목적지인가? -> D
if (n.type == 'D') {
//답 출력
System.out.println(dp[n.y][n.x]);
foundAnswer = true;
break;
}
// 3.연결된 곳을 순회 -> 좌우위아래
for (int i = 0; i < 4; i++) {
int ty = n.y + dy[i];
int tx = n.x + dx[i];
// 4.갈 수 있는가? (공통) : 맵 안에 들어오는가
if (0 <= ty && ty < R && 0 <= tx && tx < C) {
if (n.type == 'S' || n.type == '.') {
// 4.갈 수 있는가? (도슴도치) : . or D, 방문하지 않은 곳
if ((map[ty][tx] == '.' || map[ty][tx] == 'D') && dp[ty][tx] == 0) {
// 5.체크인 (고슴도치) : dp[][] = 이동거리
dp[ty][tx] = dp[n.y][n.x] + 1;
//6. 큐에 넣음
queue.add(new Node(ty, tx, map[ty][tx]));
}
} else if (n.type == '*') {
// 4.갈 수 있는가? (물) : . (물은 지나가면 알아서 방문체크됨) *물은 S도 방문가능.
if (map[ty][tx] == '.' || map[ty][tx] == 'S') {
// 5.체크인 (물) : map[][] = *
map[ty][tx] = '*';
// 6.큐에 넣음
queue.add(new Node(ty, tx, '*'));
}
}
}
}
}
if(foundAnswer){
} else {
System.out.println("KAKTUS");
}
}
}