99클럽 코테 스터디 13일차 TIL

비기너

문제

12605번: 단어순서 뒤집기

# 스택

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

풀이

문자열의 단어 순서를 거꾸로 출력하는 문제이다.

문자열을 공백을 기준으로 잘라서 스택에 넣은 후

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());

		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			Stack<String> stk = new Stack<>();
			while (st.hasMoreTokens())
				stk.push(st.nextToken());

			bw.write("Case #" + i + ": ");
			while (!stk.isEmpty())
				bw.write(stk.pop() + " ");
			bw.write("\n");
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

27961번: 고양이는 많을수록 좋다

# 그리디

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

풀이

고양이를 n마리 생성하기 위한 마법의 최소 횟수를 구하는 문제이다.

마법은 생성 마법과 복제 마법 두 가지가 존재하는데 처음에만 생성 마법으로 고양이를 생성하고 그 뒤에는 계속 복제 마법으로 고양이 수가 n마리가 될 때까지 늘려주면 된다.

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		long n = Long.parseLong(br.readLine());
		int cnt = 0;
		long tmp = 0;

		while (n != tmp) {
			cnt++;
			if (tmp == 0)
				tmp = 1;
			else if (tmp * 2 >= n)
				break;
			else
				tmp *= 2;
		}

		bw.write(cnt + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

30689번: 미로 보수

# dfs

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

풀이

미로에서 사이클을 탐색하는 문제이다.

dfs를 통해 사이클을 탐색한다.

사이클을 찾으면 사이클에 속하는 노드 중 최소인 값을 정답값에 더해준다.

visited 배열을 통해 방문 처리를 하고 ok 배열을 통해 미로에서 탈출할 수 있는 부분을 추가한다.

사이클을 찾고 비용을 구했다면 해당 노드들도 ok 배열 값을 true로 설정한다.

코드

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

public class Main {
	static int n, m, ans;
	static char[][] a;
	static int[][] c;
	static boolean[][] visited, ok;
	static char[] d = { 'U', 'D', 'L', 'R' };
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static void dfs(int y, int x) {
		visited[y][x] = true;
		for (int i = 0; i < 4; i++) {
			if (a[y][x] != d[i])
				continue;
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m || ok[ny][nx]) {
				ok[y][x] = true;
				return;
			}
			if (visited[ny][nx]) {
				int ty = y;
				int tx = x;
				int mn = 1000000000;
				while (true) {
					mn = Math.min(mn, c[ty][tx]);
					for (int j = 0; j < 4; j++) {
						if (a[ty][tx] == d[j]) {
							ty += dy[j];
							tx += dx[j];
							break;
						}
					}
					if (ty == y && tx == x)
						break;
				}
				ans += mn;
			} else
				dfs(ny, nx);
			ok[y][x] = true;
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		a = new char[n][m];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++)
				a[i][j] = s.charAt(j);
		}

		c = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++)
				c[i][j] = Integer.parseInt(st.nextToken());
		}

		visited = new boolean[n][m];
		ok = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (ok[i][j])
					continue;
				dfs(i, j);
			}
		}

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}