[백준] 2667번(python 파이썬)

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

 

---

먼저 2차원 배열을 생성할 수 있어야한다. 

graph = [list(map(int, input())) for _ in range(n)]

입력을 받으면서 그래프를 만든다.

그래프의 1의 묶음을 찾는 문제이다. 묶음을 찾는 문제들은 DFS로 구현이 가능하다.

 

---

처음 구현 코드

DFS익숙하지 않아서 이전에 풀었던 DFS틀에 맞춰서 풀지 못하였다.

 

n = int(input())

graph = [list(map(int, input())) for _ in range(n)]

def dfs(x, y, house_count):
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False

    if graph[x][y] == 1:
        graph[x][y] = house_count
        dfs(x - 1, y, house_count)
        dfs(x, y - 1, house_count)
        dfs(x + 1, y, house_count)
        dfs(x, y + 1, house_count)
        return True
    return False


result = 0
for i in range(n):
    for j in range(n):
        if dfs(i, j, result + 2):
            result += 1

house_count = [0] * result
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            house_count[graph[i][j] - 2] += 1
house_count.sort()
print(result)
for i in range(len(house_count)):
    print(house_count[i])

 

---

2번째 구현

1260문제의 DFS틀에 맞춰서 다시 작성

2차원 배열 인접 탐색을 할때 dx, dy를 사용하여 상 하 좌 우에 재귀함수를 사용한다.

상 하 좌 우가 배열을 벗어나면 continue

n = int(input())

graph = [list(map(int, input())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def Dfs(cur_x, cur_y, visited, house_count):
    visited[cur_x][cur_y] = True
    for i in range(4):
        next_x = cur_x + dx[i]
        next_y = cur_y + dy[i]
        if next_x <= -1 or next_x >= n or next_y <= -1 or next_y >= n:
            continue
        if not visited[next_x][next_y] and graph[next_x][next_y] == 1:
            house_count = Dfs(next_x, next_y, visited, house_count + 1)

    return house_count

answer_list = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and not visited[i][j]:
            answer_list.append(Dfs(i, j, visited, 1))

answer_list.sort()

print(len(answer_list))
for i in answer_list:
    print(i)