[알고리즘] DFS, BFS | 2667 단지번호 붙이기, 2606 바이러스

단지번호 붙이기

답: 

BFS 풀이

from sys import stdin
from collections import deque

input = stdin.readline

N = int(input())
graph = []
for _ in range(N):
    line = list(map(int, input().strip()))
    graph.append(line)

# {위, 아래, 오른쪽, 왼쪽} 상하좌우
dx = [0, 0, 1, -1] #(0, 1) (0, -1) (1, 0) (-1, 0)
dy = [1, -1, 0, 0]

def bfs(graph, x, y):
    queue = deque()
    # 무엇으로 시작해야하나? x랑 y를 제공해주기
    queue.append((x, y))
    # 탐색 중 1인 부분은 0으로 바꿔 다시 방문하지 않도록 한다
    graph[x][y] = 0 
	# 현재 단지의 시작 집을 +1 하고 시작
    cnt = 1 

    while queue:
	    #queue에 들어있는 노드들을 싹 확인하며 연결된 노드들 모두 세기
        a, b = queue.popleft()
        graph[a][b] = 0
        for i in range(4):
        	# 이동하고자하는 좌표값을 현재 위치에 더하기 
            next_x = a + dx[i]
            next_y = b + dy[i]

            # 그래프를 벗어나지 않도록 조건을 걸어주고, 해당 위치가 1인지 확인하여 처리
            if 0 <= next_x < N and 0 <= next_y < N and graph[next_x][next_y] == 1:
                graph[next_x][next_y] = 0
                queue.append((next_x, next_y))
                # 집 추가
                cnt += 1 
    return cnt

answer = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
        	# 시작점이 주어지지 않았으므로 [i][j]가 1인 곳을 시작점으로 삼기
            # answer list에 결과값 append 해주기
            answer.append(bfs(graph, i, j))
            

print(len(answer)) # 전체 단지 수 출력
for a in sorted(answer): # 단지마다의 집 수 출력
    print(a)

 

 

아래는 설명 없는 버전

from sys import stdin
from collections import deque

input = stdin.readline

N = int(input())
graph = []
for _ in range(N):
    line = list(map(int, input().strip()))
    graph.append(line)

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(graph, x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0 
    cnt = 1 

    while queue:
        a, b = queue.popleft()
        graph[a][b] = 0
        for i in range(4):
            next_x = a + dx[i]
            next_y = b + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N and graph[next_x][next_y] == 1:
                graph[next_x][next_y] = 0
                queue.append((next_x, next_y))
                cnt += 1 
    return cnt

answer = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            answer.append(bfs(graph, i, j))
            

print(len(answer)) 
for a in sorted(answer):
    print(a)

 

 

문제 분석 및 해석

1은 집이 있는 곳, 0은 집이 없는 곳

연결된 집을 구하는데, 좌우, 혹은 아래위로 다른 집이 있는 경우가 연결, 대각선은 연결이 아님

지도를 입력해 단지 수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 출력

 

 (** 만약 대각선이 포함인 경우는 dx, dy 좌표값에 대각선을 포함시켜 BFS를 실행하면 된다고 한다)

 

 

입력

첫줄 N = 정사각형이므로 N x N 이 입력됨

이후 N줄에 N개의 자료가 입력된다.

 

출력

1. 총 단지 수

2. 각 단지내 집 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하기

 

 

 

>> 풀이생각

BFS DFS모두로 풀이할 수 있을 것 같다

1을 찾아 이어진 부분에 대한 탐색을 실행하고, 각 단지를 append해준다

list의 길이가 총 단지의 숫자, 각 단지내 집 수가 list에 담기게 될 것임

 

 

 

===== 아래는 찾아본 풀이 방법 설명들 =====

 

어떻게 풀어야할까?

 

1. map[0][0]에서 map[N-1][N-1]까지 방문하지 않은 곳에서 dfs호출

2. 호출 전에 count를 1로 초기화 한다.

3. 연결된 단지내 집 수를 count에 더해준다.

4. 탐색이 끝나면 해당 단지의 수를 전체 단지 수에 +해준다

 

 

-> DFS BFS 둘 다로 풀이할 수 있다

1. 그래프 탐색 시작점을 알 수 없으므로 전체를 돌면서 1인 지점을 찾아서 탐색을 시작

2. 탐색 중 1인 부분은 0으로 바꿔 다시 방문하지 않도록 한다

3. 한번의 DFS혹은 BFS가 끝나면 확장이 불가능 = 단지 +1

 

 

 

리뷰.

이전에 접한 문제와 유사해서 꼭 풀이해보고 싶었다

시작점을 주지 않는 BFS DFS 문제에서 어떻게 첫 시작점을 잡는지에 대해 학습할 수 있었다.

 

 

---

바이러스

 

답: 

BFS 풀이

from sys import stdin
from collections import deque

input = stdin.readline

n = int(input())
m = int(input())

graph = [[0] * (n + 1) for i in range(n + 1)]
visited = [0] * (n + 1)

for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
def bfs(start_node):
    queue = deque([start_node])
    visited[start_node] = 1

    while queue:
        node = queue.popleft()
        for i in range(1, n + 1):
            if visited[i] == 0 and graph[node][i] == 1:
                queue.append(i)
                visited[i] = 1

bfs(1) # 함수 시작값주고 작동
answer = -1  # 1번 컴퓨터 빼기 
for v in visited:
    if v == 1:
        answer += 1 
print(answer)

 

 

DFS 풀이

from sys import stdin

input = stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(1, n + 1):
        if visited[i] == 0 and graph[v][i] == 1:
            dfs(i)

n = int(input())
m = int(input())

graph = [[0] * (n + 1) for i in range(n + 1)]
visited = [0] * (n + 1)

for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

dfs(1)

answer = -1  # 1번 컴퓨터 빼기 
for v in visited:
    if v:
        answer += 1 
print(answer)

 

 

 

문제 분석 및 해석

 

웜 바이러스, 연결되어있는 컴퓨터에게 전파됨

1번 컴퓨터가 바이러스에 걸렸을때 함께 감염된 컴퓨터 수를 출력하시오

 

 

 

>> 풀이생각

1번 컴퓨터는 세지 않고, 나머지 감염된 컴퓨터를 세어 출력해야한다.

 

연결된 그래프만 잘 탐색하면 되므로 DFS BFS 둘다 풀이가 가능하다.

 

 

리뷰.

graph를 만드는 방법을 상세히 배울 수 있었다.

graph를 행렬처럼 생성하여 연결된 간선을 표현하는 것인데,

이렇게 구현할 경우 i * i 위치에 있는 요소는 모두 0이며, 이 i * i 를 선분으로 이었을때 대칭이 되는 모습을 확인 할 수 있다.

 

ex

만들어진 graph를 출력하면 이렇게 나온다!

 

 

 

---

 

 

이번 주는 BFS DFS에 익숙해지기 위해 매일 1문씩은 도전해보았는데, 기본 식은 익혔어도 활용에 약하다는 것을 계속 느꼈다..

클론 코딩으로 풀이한 문제들도 있어서 시간이 지나고나서 문제를 다시 풀어보기로 했다.