Feel Coding

단계별로 풀어보기 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 해줘서 차곡차곡 넣어주었다.

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

이번에는 파이썬으로 풀어봤다.

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):
        visited = [False] * (len(self.data) + 1)
        stack = []
        stack.append(start)
        while stack:
            cur = stack.pop()
            if not visited[cur]:
                print(cur, end=" ")
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            temp.reverse()
            stack.extend(temp)
    def bfs(self, start):
        import collections
        visited = [False] * (len(self.data) + 1)
        queue = collections.deque()
        queue.append(start)
        while queue:
            cur = queue.popleft()
            if not visited[cur]:
                print(cur, end=' ')
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            queue.extend(temp)
from sys import stdin

node_edge_start = list(map(int, stdin.readline().split()))
graph = Graph(node_edge_start[0])
li = []
for i in range(0, node_edge_start[1]):
    rawInput = list(map(int, stdin.readline().split()))
    graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(node_edge_start[2])
print()
graph.bfs(node_edge_start[2])