실버벨의 Stack Overflow

programmers.co.kr/learn/courses/30/lessons/43162

DFS 와 BFS 두 가지로 문제를 해결해 봤다.

BFS

package eun;

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		int[][] computers  = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		int n = 3;
		solution(n, computers);
	}
	
	public static int solution(int n, int[][] computers) {
		int answer = 0;
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[n];
		
		// 시작점 for 문
		for (int i=0; i<n; i++) {
			if (!visited[i]) {
				q.add(i);
				
				while(!q.isEmpty()) {
					int cur = q.poll();
					visited[cur] = true;
					
					// 시작점에서 갈 수 있는곳 탐색
					for (int j=0; j<n; j++) {
						if(!visited[j] && computers[cur][j] == 1) q.add(j);
					}
				}
				
				answer++;
			}
		}
		System.out.println(answer);
		return answer;
    }
}

DFS

package eun;

public class Eun {
	public static int answer =0;
	public static int[] dx = { 0, 1, 0, -1 };
	public static int[] dy = { 1, 0, -1, 0 };
	public static void main(String[] args) {
		int[][] computers  = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		//int[][] computers  = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
		int n = 3;
		
		solution(n, computers);
	}
	
	public static int solution(int n, int[][] computers) {
		
        for(int y=0; y<n; y++) {
        	for(int x=0; x<n; x++) {
        		if(computers[y][x] == 1) {
        			dfs(x, y, computers, n);
        			answer++;
        		}
        	}
        }
        System.out.println(answer);
		return answer;
    }
	
	public static void dfs(int x, int y, int[][] computers, int n) {
		computers[y][x] = 0;
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (computers[ny][nx] == 0) continue;
			dfs(nx, ny, computers, n);
		}
	}
	
}

문제 링크

그리디(Greedy)

package eun;

// 알파벳은 모두 더하고,
// 이동경로의 최소를 찾는 문제

public class Solution {
	static public int solution(String name) {
        int answer = 0;
        
        int len = name.length();
        
        //최대로 가질 수 있는 min값은 끝까지 가는것
        int min_move = len-1;
        
        for(int i=0; i<len; i++) {
        	answer += Math.min(name.charAt(i)-'A', 'Z'-name.charAt(i)+1);
        	
        	//BEAABA
            //012345
        	
        	//좌우: 연속된 A의 등장에 따라 최소 움직임이 달라진다
        	int next = i+1;// 현재 다음 위치부터
        	//내 다음이 A라면 계속 NEXT++
        	while(next<len && name.charAt(next) == 'A')
        		next++;
        	
        	min_move = Math.min(min_move, i+len-next + i);
        }//for
        
        answer += min_move;
        
        return answer;
    }
	
    
	public static void main(String[] args) {
		System.out.println(solution("BEAABA"));
	}
}

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

1. 문제 이해

(0,0) 의 좌표부터 (m,n) 좌표 까지 이동할 때 최소경우의 수를 구하는 문제입니다.

2. 접근 방법

- 완전 탐색을 하되, 갔던곳을 다시 가지 않기 위해 큐를 사용해서 문제를 해결하고자 했습니다.

- 큐가 가지는 자료구조를 만들기 위해 Node라는 클래스를 만들었습니다.

3. 문제 해결

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

1. 문제 이해

 삼성 기출 문제 입니다. 

 시뮬레이션 문제인데, 과정을 자세히 보면 dfs와는 다른것을 볼 수 있습니다.

처음에 이 문제를 dfs로 접근 하였다가 멘토님의 도움으로 while문으로 해결하는 문제라는것을 깨닳았습니다.

(그러니... 꼭 다시 풀어보자!!)

2. 접근 방법

 문제의 루틴대로 따라가면서 while문을 작성해 봅시다.

여기서 핵심은 flag!!

1) 4방향을 모두 탐색하였는데, 청소할곳(0)을 못찾은 경우에 루틴으로 가기 위한 flag!

2) 뒤로 가봤는데 뒤에가 벽인 경우는 탈출할수 있도록!!

3) 뒤로 가봤는데 뒤에가 벽이 아닌 경우는 방향을 그대로 가져 가도록 합시다!!

위에 3가지를 생각하면서 코딩에 들어가면 문제 끄~~~읏!!!

3. 문제 해결

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

1. 문제 이해

 이 문제를 풀면서 하나 깨닳은 것은 문제 이해가 개인적으로 정말 중요하다는것을 느꼈습니다....

 뱀문제와 마찬가지로 시뮬레이션 문제 입니다.

2. 접근 방법

[1 단계] 입력되는 dir변수에 따라서 시계방향으로 돌지, 반 시계방향으로 돌지 정하게 됩니다.

[2 단계] 왼쪽, 오른쪽을 검사하여 서로 다른 값이 있다면 반대방향으로 돌려주고, 

                                   서로 같은 값이 있다면 돌려 움직이지 않습니다.

=> 저같은 경우는 이 부분을 왼쪽 오른쪽 으로 나눠서 재귀로 작성하였습니다.

cf> 이 부분에서 논리적으로 잘못생각하여 시간이 꽤 걸렸습니다.

 돌리기전에 양옆을 먼저 확인하여 옆 톱니가 움직이는지 여부를 먼저 결정해줘야 합니다!!!

[3 단계] 12시 방향에 있는것들의 가중치를 곱해 답을 출력합니다.

3. 문제 해결

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

1. 문제 이해

 벽을 3개 세웠을때, 바이러스가 퍼지고, 그후 바이러스에 전염되지 않은지역을 세는 문제입니다. 이때, 전염되지 않은 지역이 최대가 되는 경우를 알아내는 문제입니다. 

2. 접근 방법

 n이 8보다 작은수 이므로 완전 탐색으로 해결했습니다.

[1단계] dfs로 벽 세우기 (for문을 사용한 완전 탐색)

[2단계] 벽이 3개가 됐을때, bfs로 바이러스 확장시키기

[3단계] 바이러스를 퍼지기 전으로 회복시키면서 전염이 안된 지역 세어주기

3. 문제 해결

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

1. 문제 이해

L 시간동안 탈주범이 있을 수 있는 공간의 갯수를 세어보는 문제입니다.

2. 접근 방법

- dfs를 통해 문제에 접근하였습니다.

- 4방향으로 나누어 현재와 다음단계의 파이프를 비교하여 갈수 없는곳을 continue 시켰습니다.

- ret 이라는 변수를 따로 두어 지나간 곳을 1로 체크하여 1이 체크된 곳의 수를 세어 출력하였습니다.

(visit은 ret과 다른 용도 입니다. ret을 쓰지 않으면 갔던곳을 또 갈수 없기 때문에 1번(+)파이프일 경우에 오류가 생기게 됩니다.)

3. 문제 해결

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

1. 문제 이해

 모음 1개와 자음 2개 이상이 꼭 포함 된다는 것을 기억해야 합니다.

2. 접근 방법

로또 (http://sbell92.tistory.com/15?category=640303) 문제와 비슷한 방법으로 접근했습니다.

dfs를 이용해 완전 탐색을 하되, 모음과 자음일 경우를 고려해 주었습니다.

3. 문제 해결

※ 오늘의 코드 리뷰 : 벡터가 점점 익숙해져 갑니다. ㅎㅎ

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

1. 문제 이해

 길이가 n인 정사각형의 맨 밖깥 부분에만 숫자가 써져 있고 그 안에는 #으로 지뢰가 가려져 있습니다. 

지뢰가 최대로 있을 경우를 구하는 문제입니다.

2. 접근 방법

 #부분을 공략하는 것이 이 문제의 point 입니다.

1. # 부분을 완전 탐색 합니다.

2. #부분의 8방향에 0이 하나라도 있다면 # 부분에는 지뢰가 없습니다.

3. #부분의 8방향이 0이 하나도 업다면 카운트를 올려주고, 주변 8방향을 -1 해줍니다.

3. 문제 해결