내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/77486

기본적인 DFS로 구현이 가능한 문제입니다.

입력에 따라 판매원들의 이름을 Dictionary에 저장해서 Index화 해줍니다. 

이후 판매원들의 referral을 입력받아 자신을 초대한 사원을 가리키게 해주면 위로만 타고 올라가지는 그래프 형태의 구조가 됩니다.

이제 매출이 발생한 입력마다 위로 타고 올라가며 상납금(?)을 더해주면 됩니다.

11~13번에서 런타임 에러가 발생한다면 해당 테스트케이스의 사원들의 초대 형태가 일렬로 길게 이어진 모양이라 타고 올라가다가 스택 오버플로우가 발생한 것입니다.

종료조건이 제대로 잡히지 않았을때 자주 발생하는 에러인데, 생각해 보면 판매에서 얻어지는 이익의 최댓값은 10000입니다. (칫솔 하나의 이익이 100원, 판매수의 최대가 100)

상납금은 10%씩을 납부하는데, 가장 큰 이익이 발생해도 몇 단계만 올라가면 상납금은 0원이 됩니다.

10000 (매출 발생) -> 1000원 상납 -> 100원 상납 -> 10원 상납 -> 1원 상납 -> 0원 상납 (판매자의 5단계 위는 돈을 얻을 수 없다!)

따라서 상납금이 0원이 되는 경우 다음 호출을 하지 않도록 탈출 조건을 잡아주면 됩니다.

if lead == -1 or tax == 0: (돈을 보낼 초대자가 존재하지 않거나, 보낼 돈이 0원일시 더 이상 호출하지 않음)

def solution(enroll, referral, seller, amount):
    result = [0 for i in range(len(enroll))]
    follow = [-1 for i in range(len(enroll))]
    name_dict = {}

    index = 0
    for name in enroll:
        name_dict[name] = index
        index += 1

    for i in range(len(referral)):
        if referral[i] != '-':
            target = name_dict[referral[i]]
            follow[i] = target

    for i in range(len(seller)):
        start = name_dict[seller[i]]
        money = amount[i] * 100
        send_money(follow, result, money, start)

    return result


def send_money(follow, result, money, me):
    lead = follow[me]
    tax = int(money / 10)
    result[me] += money - tax

    if lead == -1 or tax == 0:
        return
    else:
        send_money(follow, result, tax, lead)

https://school.programmers.co.kr/learn/courses/30/lessons/43162

기본적인 DFS로 풀이가능한 문제입니다.

이 문제도 기본유형의 문제라 레벨이 높은 상태인것 같습니다.

아직 탐색하지 않은 computer를 만나면 DFS로 연결된 모든 컴퓨터들을 탐색하고, 방문처리해주면 됩니다.

DFS 한번에 연결된 컴퓨터들이 전부 방문되기 때문에 정답인 네트워크의 갯수는 DFS의 호출횟수와 같습니다.

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            findNetwork(i, computers, visited)
            answer += 1

    return answer


def findNetwork(now, computers, visited):
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and not visited[next]:
            visited[next] = True
            findNetwork(next, computers, visited)
            


print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

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

구현을 신경써야 하는 문제입니다.

문제를 2개의 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 다리 만들기

1번은 BFS DFS아무것이나 원하는 방법으로 구현하면 됩니다.

2번의 경우는 BFS를 이용하는것이 구현과 이해가 간편합니다.

시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.

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 q2146_BOJ_다리만들기 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int[] parent;
	static int N;

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

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				if (map[n][m] == -1) {
					dfs(n, m, island);
					island++;
				}
			}
		}

		int answer = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][N];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m });
						visit[n][m] = true;
					}
				}
			}

			int l = 0;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {

					int[] now = queue.poll();
					int x = now[0];
					int y = now[1];

					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY]) {

							if (map[nX][nY] == 0) {
								queue.offer(new int[] { nX, nY });
								visit[nX][nY] = true;
							} else {
								answer = Math.min(answer, l);
								visit[nX][nY] = true;
							}
						}
					}
				}
				l++;
				if (l > answer) {
					queue.clear();
				}
			}
		}
		System.out.println(answer);

	}

	static void dfs(int x, int y, int name) {
		map[x][y] = name;

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY) && map[nX][nY] == -1) {
				dfs(nX, nY, name);
			}
		}

	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}
}

https://programmers.co.kr/learn/courses/30/lessons/1831

원래는 이분탐색의 Lv.4 문제를 풀려고 했는데, 저도 구현하다가 애매한 부분이 있어 확인해보니 문제에 오류가 있다는 얘기가 많아서 다른 Lv.4 문제를 가져왔습니다.

연산후의 값이 주어지고 그 값이 연산을 통해 만들 수 있는가를 검증하거나 가능한 경우의 수를 찾는 문제는 주어진 값부터 연산을 거꾸로 짚어가며 풀이하면 쉽고 빠르게 풀리는 경우가 많습니다. 이번 문제도 그런 유형이었는데요.

처음엔 3단고음이라는 연산이 중첩되어 계산되는 것을 stack처럼 중첩의 갯수를 카운팅해서 풀이하려고 했는데 구현 난이도가 어마어마 했을 뿐만 아니라 통과도 실패했습니다.

QnA의 도움을 얻어, 이 3단고음이라는 연산은 뒤에서부터 읽어들어갈때, +의 갯수가 2개보다 큰 경우 *하나와 묶어서 사라질 수 있다는걸 알았습니다. 즉, 거꾸로 3단고음 연산이 동작할때 1을 뺄때 +의 갯수를 늘려주고 (+를 역산), +의 갯수가 두개이상이면 3으로 나눠지면서 두개와 소멸하고, 초기값인 1에 도달했을때 +와 *가 모두 상쇄되었으면 카운트를 1 늘려주었습니다.

재귀호출 중간에 ++의 갯수만큼 *의 역산이 이루어져야 하는데 불가능한 경우 가지치기 했습니다.

해당 아이디어를 바탕으로 dfs를 응용한 재귀문을 작성해 테스트케이스를 통과했습니다.

테스트케이스가 하나뿐이라 예외에 걸릴지는 잘 모르겠네요.

public class q1831_Programmers_4단고음 {
	static int answer;

	public static void main(String[] args) {

//		int[] input = { 15, 24, 41 };
		int[] input = { 15, 24, 41, 2147483647 };

		for (int i = 0; i < input.length; i++) {
			System.out.println(solution(input[i]));
		}
	}

	private static int solution(int n) {
		answer = 0;

		dfs(n, 0);

		return answer;
	}

	private static void dfs(int now, int depth) {
		//System.out.println("now:" + now + "   depth:" + depth);
		
		if (now == 1 && depth == 0) {
			answer++;
			return;
		}
		
		if (now < Math.pow(3, (depth / 2))) {
			return;
		}

		dfs(now - 1, depth + 1);
		
		if (depth >= 2 && now >= 3 && now % 3 == 0) {
			dfs(now / 3, depth - 2);
		}

	}

}