Feel Coding

단계별로 풀어보기 DFS와 BFS의 6단계 문제

한 시간 정도 걸렸던 것 같다.

최솟값을 구하는 거니까 BFS를 이용했다.

from sys import stdin
m, n = list(map(int, stdin.readline().split()))
matrix = []
count = 0
minus = 0
zero = 0
import collections
q = collections.deque()
one = []
for i in range(n):
    temp = list(map(int, stdin.readline().split()))
    matrix.append(temp)
    count += temp.count(1)
    minus += temp.count(-1)
    zero += temp.count(0)
    for j in range(m):
        if temp[j] == 1:
            q.append((i, j, 0))
if zero == 0:
    print(0)
else:
    ripen = 0
    result = 0
    visited = [[False] * m for i in range(n)]
    while q:
        cur = q.popleft()
        if not visited[cur[0]][cur[1]]:
            visited[cur[0]][cur[1]] = True
            matrix[cur[0]][cur[1]] = 1
            ripen += 1
            result = cur[2]
        else:
            continue
        if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == 0 and not visited[cur[0] + 1][cur[1]]:
            q.append((cur[0] + 1, cur[1], cur[2] + 1))
        if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == 0 and not visited[cur[0]][cur[1] + 1]:
            q.append((cur[0], cur[1] + 1, cur[2] + 1))
        if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == 0 and not visited[cur[0] - 1][cur[1]]:
            q.append((cur[0] - 1, cur[1], cur[2] + 1))
        if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == 0 and not visited[cur[0]][cur[1] - 1]:
            q.append((cur[0], cur[1] - 1, cur[2] + 1))
    if ripen == m * n - minus:
        print(result)
    else:
        print(-1)

단계별로 풀어보기 DFS와 BFS의 5단계 문제

BFS로 풀면 된다.

큐에 (row, col, depth)를 집어넣는다. (row, col)은 방문한 위치, depth는 (1, 1)부터 몇 칸 거쳐서 왔는지 정보이다.

from sys import stdin
import collections
n, m = list(map(int, stdin.readline().split()))
matrix = []
for i in range(n):
    matrix.append(stdin.readline())
q = collections.deque()
q.append((0, 0, 1))
visited = [[False] * m for i in range(n)]
while q:
    cur = q.popleft()
    if not visited[cur[0]][cur[1]]:
        visited[cur[0]][cur[1]] = True
        if cur[0] == n - 1 and cur[1] == m - 1:
            print(cur[2])
            break
    else:
        continue
    if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == "1" and not visited[cur[0] + 1][cur[1]]:
        q.append((cur[0] + 1, cur[1], cur[2] + 1))
    if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == "1" and not visited[cur[0]][cur[1] + 1]:
        q.append((cur[0], cur[1] + 1, cur[2] + 1))
    if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == "1" and not visited[cur[0] - 1][cur[1]]:
        q.append((cur[0] - 1, cur[1], cur[2] + 1))
    if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == "1" and not visited[cur[0]][cur[1] - 1]:
        q.append((cur[0], cur[1] - 1, cur[2] + 1))

단계별로 풀어보기 if문의 1단계 문제

너무 쉬운 문제라서 올리기도 민망하지만

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        if (a > b)
            System.out.println(">");
        else if (a < b)
            System.out.println("<");
        else System.out.println("==");
    }
}

단계별로 풀어보기 그리디 알고리즘의 마지막(4단계) 문제

더하기끼리 최대한 많이 묶으면 된다.

import java.awt.datatransfer.StringSelection;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        StringTokenizer st = new StringTokenizer(s, "-");
        ArrayList list = new ArrayList<>();
        while (st.hasMoreTokens()) {
            String next = st.nextToken();
            if(next.contains("+")) {
                StringTokenizer tokenizer = new StringTokenizer(next, "+");
                int sum = 0;
                while (tokenizer.hasMoreTokens()) {
                    sum += Integer.parseInt(tokenizer.nextToken());
                }
                list.add(sum);
            }
            else {
                list.add(Integer.parseInt(next));
            }
        }
        int result = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            result -= list.get(i);
        }
        System.out.println(result);
    }
}

단계별로 풀어보기 그리디 알고리즘 2단계 문제

파이썬의 좋은 점 중 하나가 (x, y)와 같은 순서쌍을 표현하고 싶을 때 클래스를 따로 만들지 않고 튜플을 이용하면 된다는 점인 것 같다.

자바는 튜플이 없어서 클래스를 하나 만들었다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList li = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            li.add(new Tuple(in.nextInt(), in.nextInt()));
        }
        li.sort(new Comparator() {
            @Override
            public int compare(Tuple o1, Tuple o2) {
                if (o1.y - o2.y < 0)
                    return -1;
                else if (o1.y - o2.y > 0)
                    return 1;
                else
                    return o1.x - o2.x;
            }
        });
        ArrayList order = new ArrayList<>();
        int count = 0;
        order.add(li.get(0));
        count++;
        for (int i = 1; i < n; i++) {
            if(order.get(count - 1).y <= li.get(i).x) {
                count++;
                order.add(li.get(i));
            }
        }
        System.out.println(count);
    }
}
class Tuple {
    int x;
    int y;

    public Tuple(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

단계별로 풀어보기 그리디 알고리즘의 3단계 문제

운영체제에서도 배운 SJF(Shortest Job First)로 하면 기다리는 시간이 최소가 된다.

from sys import stdin
n = int(input())
time = list(map(int, stdin.readline().split()))
time.sort()
acc = [0] * n
acc[0] = time[0]
for i in range(1, n):
    acc[i] = acc[i - 1] + time[i]
total = 0
for i in range(n):
    total += acc[i]
print(total)

단계별로 풀어보기 그리디 알고리즘의 1단계 문제

이번학기 알고리즘 수업에서 그리디 알고리즘 단원에 들어갈 때 첫번째로 배운 예제여서 어떻게 푸는지는 당연히 알고 있었다.

동전의 가치가 높은 순으로 정렬하고 그 동전을 추가시켰을 때 원하는 금액이 넘지 않으면 추가시키고 아니면 그 다음 동전에서 그 과정을 반복한다.

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
value = []
for i in range(n):
    value.append(int(input()))
total = 0
count = 0
while total != k:
    for j in range(n - 1, -1, -1):
        if total + value[j] <= k:
            total += value[j]
            count += 1
            break
print(count)

이렇게 제출했더니 시간초과가 났다. 무한루프에 빠진걸까?

혹시 몰라서 똑같은 코드를 언어만 자바로 바꿔서 이렇게 제출했더니

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
        }
        int remain = k;
        int count = 0;
        int start = n - 1;
        while (remain != 0) {
            for (int j = start; j >= 0; j--) {
                if(remain >= value[j]) {
                    int temp = remain / value[j];
                    remain = remain % value[j];
                    count += temp;
                    start = j;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

성공이었다.

이유를 모르겠다. 자바가 파이썬보다 빠른가? 흠

파이썬 코드를 조금 개선해서 이렇게 제출했더니

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
value = []
for i in range(n):
    value.append(int(input()))
remain = k
count = 0
start = n - 1
while remain != 0:
    for j in range(start, -1, -1):
        if remain >= value[j]:
            temp, remain = divmod(remain, value[j])
            count += temp
            start = j
            break
print(count)

60ms로 성공이었다.

정말로 자바가 파이썬보다 빠른가 싶어서 이 똑같은 코드를 자바로 이렇게 제출해보았다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            value[i] = in.nextInt();
        }
        int remain = k;
        int count = 0;
        int start = n - 1;
        while (remain != 0) {
            for (int j = start; j >= 0; j--) {
                if(remain >= value[j]) {
                    int temp = remain / value[j];
                    remain = remain % value[j];
                    count += temp;
                    start = j;
                    break;
                }
            }
        }
        System.out.println(count);
    }
}

성공이긴 한데 파이썬보다는 느린 104ms로 성공이었다.

정말 뭐지? 첫번째 코드는 왜 시간초과가 난걸까

단계별로 풀어보기 DFS와 BFS의 4단계 문제이다

3단계 문제인 2667번과 입출력 방법 말고는 거의 같아서 쉽게 풀 수 있었다.

오히려 배추 개수를 출력할 필요가 없어서 더 쉬웠다.

def dfs(row, col):
    if li[row][col] == 0 or visited[row][col]:
        return 0
    stack = []
    stack.append((row, col))
    while stack:
        cur = stack.pop()
        visited[cur[0]][cur[1]] = True
        if li[cur[0] - 1][cur[1]] == 1 and not visited[cur[0] - 1][cur[1]]:
            if 1 <= cur[0] - 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] - 1, cur[1]))
        if li[cur[0] + 1][cur[1]] == 1 and not visited[cur[0] + 1][cur[1]]:
            if 1 <= cur[0] + 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] + 1, cur[1]))
        if li[cur[0]][cur[1] - 1] == 1 and not visited[cur[0]][cur[1] - 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] - 1 <= m:
                stack.append((cur[0], cur[1] - 1))
        if li[cur[0]][cur[1] + 1] == 1 and not visited[cur[0]][cur[1] + 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] + 1 <= m:
                stack.append((cur[0], cur[1] + 1))
    return 1

test_case = int(input())
from sys import stdin

for i in range(test_case):
    m, n, k = list(map(int, stdin.readline().split()))
    li = [[0] * m for j in range(n)]
    for j in range(0, k):
        rawInput = list(map(int, stdin.readline().split()))
        li[rawInput[1]][rawInput[0]] = 1
    li.insert(0, [0] * (m + 2))
    li.append([0] * (m + 2))
    for j in range(1, n + 1):
        li[j].insert(0, 0)
    for j in range(1, n + 1):
        li[j].append(0)
    visited = [[False for j in range(m + 2)] for i in range(n + 2)]
    count = 0
    for j in range(1, n + 1):
        for l in range(1, m + 1):
            count += dfs(j, l)
    print(count)

단계별로 풀어보기 DFS와 BFS의 3단계 문제

dfs로 풀었는데 시간이 꽤 많이 걸렸다. 두 시간 넘게 걸린 것 같다.

그래프의 탐색이나 이렇게 배열이 주어졌을 때의 탐색이나 방법은 똑같은데 괜히 복잡하게 생각한 것 같다.

덕분에 이제 dfs가 조금 익숙해진 것 같다.

def dfs(row, col, clist):
    if li[row][col] == '0' or visited[row][col]:
        return 0
    stack = []
    stack.append((row, col))
    c = 0
    while stack:
        cur = stack.pop()
        if not visited[cur[0]][cur[1]]:
            visited[cur[0]][cur[1]] = True
            c += 1
        if li[cur[0] - 1][cur[1]] == '1' and not visited[cur[0] - 1][cur[1]]:
            if 1 <= cur[0] - 1 <= n and 1 <= cur[1] <= n:
                stack.append((cur[0] - 1, cur[1]))
        if li[cur[0] + 1][cur[1]] == '1' and not visited[cur[0] + 1][cur[1]]:
            if 1 <= cur[0] + 1 <= n and 1 <= cur[1] <= n:
                stack.append((cur[0] + 1, cur[1]))
        if li[cur[0]][cur[1] - 1] == '1' and not visited[cur[0]][cur[1] - 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] - 1 <= n:
                stack.append((cur[0], cur[1] - 1))
        if li[cur[0]][cur[1] + 1] == '1' and not visited[cur[0]][cur[1] + 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] + 1 <= n:
                stack.append((cur[0], cur[1] + 1))
    clist.append(c)
    return 1
n = int(input())
from sys import stdin

li = []
clist = []
for i in range(n):
    rawInput = stdin.readline()
    li.append(list(rawInput))
    li[i].insert(0, '0')
li.insert(0, [0] * (n + 2))
li.append([0] * (n + 2))
for i in range(1, n + 1):
    li[i][n + 1] = '0'
visited = [[False for j in range(n + 2)] for i in range(n + 2)]
count = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        count += dfs(i, j, clist)
clist.sort()
print(count)
for i in clist:
    print(i)

27일 뒤 C++로 다시 풀어보기

다시 풀어보니 정말 쉽게 풀었다.

#include <iostream>
#include <tuple>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;


int main() {
	int n;
	cin >> n;
	vector<string> map(n);
	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}
	vector<int> countApartment;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == '1') {
				queue<pair<int, int>> q;
				q.push(make_pair(i, j));
				int count = 0;
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					if (map[cur.first][cur.second] == '1') {
						map[cur.first][cur.second] = '2';
						count++;
						if (cur.first - 1 >= 0 && map[cur.first - 1][cur.second] == '1') {
							q.push(make_pair(cur.first - 1, cur.second));
						}
						if (cur.first + 1 < n && map[cur.first + 1][cur.second] == '1') {
							q.push(make_pair(cur.first + 1, cur.second));
						}
						if (cur.second - 1 >= 0 && map[cur.first][cur.second - 1] == '1') {
							q.push(make_pair(cur.first, cur.second - 1));
						}
						if (cur.second + 1 < n && map[cur.first][cur.second + 1] == '1') {
							q.push(make_pair(cur.first, cur.second + 1));
						}
					}
				}
				countApartment.push_back(count);
			}
			else continue;
		}
	}
	sort(countApartment.begin(), countApartment.end());
	cout << countApartment.size() << endl;
	for (int i = 0; i < countApartment.size(); i++) {
		cout << countApartment[i] << endl;
	}
	return 0;
}

단계별로 풀어보기 DFS와 BFS의 2단계 문제

파이썬과 C++로 풀어보았다.

파이썬 코드

class Graph:
    def __init__(self, n):
        self.data = {}
        for i in range(1, n + 1):
            self.data[i] = set()
    def add_edge(self, n, m):
        self.data[n].add(m)
        self.data[m].add(n)
    def dfs(self, start):
        count = 0
        visited = [False] * (len(self.data) + 1)
        stack = []
        stack.append(start)
        while stack:
            cur = stack.pop()
            if not visited[cur]:
                count += 1
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            temp.reverse()
            stack.extend(temp)
        print(count - 1)

from sys import stdin

nodeCount = int(input())
edgeCount = int(input())
graph = Graph(nodeCount)
li = []
for i in range(0, edgeCount):
    rawInput = list(map(int, stdin.readline().split()))
    graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(1)

C++ 코드

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;

vector<int> w[101];
vector<bool> visited(101);


int main() {
	int numOfComputers;
	cin >> numOfComputers;
	int numOfEdge;
	cin >> numOfEdge;
	for (int i = 0; i < numOfEdge; i++) {
		int n, m;
		cin >> n >> m;
		w[n].push_back(m);
		w[m].push_back(n);
	}
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (!visited[cur]) {
			visited[cur] = true;
			for (int i : w[cur]) {
				q.push(i);
			}
		}
	}
	int count = 0;
	for (int i = 1; i <= numOfComputers; i++) {
		if (visited[i]) count++;
	}
	cout << count - 1;
	return 0;
}

2월 4일에 이렇게 풀고 두 달 뒤인 4월 7일에 C++로 다시 풀어보았다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;


int main() {
	int numOfComputers, n;
	cin >> numOfComputers >> n;
	vector<int> v[101];
	vector<bool> visited(numOfComputers + 1);
	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	stack<int> s;
	s.push(1);
	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		visited[cur] = true;
		for (int i = 0; i < v[cur].size(); i++) {
			if (!visited[v[cur][i]]) {
				s.push(v[cur][i]);
			}
		}
	}
	int cnt = 0;
	for (int i = 2; i <= numOfComputers; i++) {
		if (visited[i] == true)
			cnt++;
	}
	cout << cnt;
	return 0;
}

이번에는 DFS로 풀어보았다. 막 다른 길이 나왔을 때 가지치기를 빨리 하라고 DFS를 쓰긴 했는데 DFS를 쓰나 BFS를 쓰나 별 차이는 없을 것 같다.

이 문제는 가중치가 없는 무방향 그래프에서 1부터 탐색을 하면 된다. 그렇게 방문된 노드의 수에서 1을 빼면 그게 바이러스에 걸린 컴퓨터 대수이다. 바이러스든 뭐든 퍼트리는 것은 다 DFS, BFS라고 생각하면 된다.

그래프를 저장하는 방법은 벡터를 사용했다. 벡터의 배열을 사용해서 노드 i와 연결된 노드들은 v[i] 벡터에 push_back 해줘서 차곡차곡 넣어주었다.