백준) 그래프, 문자열

백준 16956번 늑대와 양

---

내가 떠올린 풀이 해설

처음 이 문제를 봤을 때 늑대 기준으로 탐색을 하려고 했다. 문제를 해결하려고 했으나 답이 나오지 않아 블로그를 참고했다. 블로그 풀이는

늑대랑 양이랑 한 칸 떨어져 있으면 울타리로 감싸면 됨, 울타리 갯수 제한 없음, 늑대랑 양이랑 바로 옆만 아니면 양은 무조건 지킬 수 있음을 떠올려서 늑대 주변에 울타리만 감싸주었다. 예제 출력이랑 다르게 나오는데 정답이 나왔다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek16956 {
	static int []dx = {1, 0, -1, 0};
	static int []dy = {0, -1, 0, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		char[][]arr = new char[n][m];
		boolean flag = true;
		
		for(int i = 0; i < n; i++) {
			String tmp = br.readLine();
			for(int j = 0 ; j < m; j++) {
				arr[i][j] = tmp.charAt(j);
			}
		}
		for(int i = 0 ; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(arr[i][j] == 'W') {
					for(int r = 0; r < 4; r++) {
						int nx = i + dx[r];
						int ny = j + dy[r];
						
						if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
							if(arr[nx][ny] == '.') {
								arr[nx][ny] = 'D';
							}
							else if(arr[nx][ny] ==  'S') {
								flag = false;
								System.out.println(0);
								return;
							}
						}
					}
				}
			}
		}
		if(!flag) {
			System.out.println(0);
		}
		else {
			StringBuilder sb = new StringBuilder();
			System.out.println(1);
			for(int i = 0 ; i < n; i++) {
				sb.append(arr[i]);
				sb.append("\\n");
			}
			System.out.println(sb);
		}
	}
}

---

백준 1152 단어의 개수

---

내가 떠올린 풀이 해설

String으로 받아서 StringTokenizer로 공백 기준으로 자르고 StringTokenizer의 개수를 세는 countTokens로 출력해주면 된다.

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek1152 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		
		StringTokenizer st = new StringTokenizer(str);
		System.out.println(st.countTokens());

	}
}

---

백준 1764번 듣보잡

---

내가 떠올린 풀이 해설

HashSet을 이용해 N번 까지 HashSet에 넣고 정답을 출력하는 ArrayList을 만들고 br.readLine을 담을 수 있는 String tmp 변수를 만들어서 contains으로 HashSet에 tmp가 있으면 ArrayList에 add 하는 방식으로 풀었다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1764 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		HashSet<String> set = new HashSet<>();
		for(int i = 0; i < n; i++) {
			set.add(br.readLine());
		}
		
		ArrayList<String> answer = new ArrayList<>();
		for(int i = 0; i < m; i++) {
			String tmp = br.readLine();
			if(set.contains(tmp)) {
				answer.add(tmp);
			}
		}
		Collections.sort(answer);
		System.out.println(answer.size());
		for(int i = 0; i < answer.size(); i++) {
			System.out.println(answer.get(i));
		}
	}
}

---

오늘의 회고

오늘은 문자열과 그래프 문제를 풀었습니다. 쉬운 문제들로 풀려고 했는데 늑대와 양 문제에서 막혔습니다. 3주째 알고리즘을 풀고 있는데 꾸준히 문제를 풀고 있어서 진도에서는 만족을 하는데 실력에서는 아직 불만족입니다. 꾸준히 공부하면 실력도 성장할 것이라 믿고 지치지 않고 꾸준히 알고리즘을 풀어나가겠습니다.

 

참고 블로그

https://go-coding.tistory.com/77