4 분 소요

Graph

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘ ’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘ ’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, ‘-‘와 ’ ‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

4 4
----
----
----
----

예제 출력 1 복사

4

예제 입력 2 복사

6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

예제 출력 2 복사

31

예제 입력 3 복사

78
|------|
||----||
|||--|||
||----||
|------|

예제 출력 3 복사

13

예제 입력 4 복사

10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||

예제 출력 4 복사

41

예제 입력 5 복사

6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-

예제 출력 5 복사

19

스스로 고민

  • 우선 N x M 의 배열을 만들어준다.
  • 그래프로 풀어야 되는데 막상 어떻게 풀지 전혀 모르겠다
  • -- 가 만났을 때 처리를 어떻게 해야 되고 아래 위로 || 가 있을 경우를 어떻게 처리 하는 게 좋을지 감이 안 왔다.
  • -- 두 개가 만난다면 다른 문자로 표기하고 넘어가야 되나?
  • 그러면 어떻게 표시를 해야 작동하는데 문제가 없고 편리할까
  • 근데 또 위아래는 어떤 방식으로 표현을 해야 할까

이런 고민을 하는 건 재밌지만 이제 CS 공부도 하기로 했고 팀 프로젝트 등 할 게 많아서 딱 한 시간 고민해보고 답 안 나오면 답지 보면서 풀기로 했다 (실버 단계 까지만)

스스로 이런 문제를 못 푼다는 게 너무 짜증 났지만 힙 처럼 이것도 결국에는 할 수 있을 거라 믿고 확실하게 이해하고 넘어가자

구현 코드

(다른 사람 코드 봤음)

import sys

def dfs(x, y):
    if graph[x][y] == '-':
        graph[x][y] = 1
        for _y in [1, -1]:
            Y = y+ _y
            
            if (Y > 0 and Y < m) and graph[x][Y] == "-":
                dfs(x, Y)
    if graph[x][y] == '|':
        graph[x][y] = 1
        for _x in [1, -1]:
            X = x + _x
            if (X > 0 and X < n) and graph[X][y] == '|':
                dfs(X, y)
                

n, m = map(int, sys.stdin.readline().split())

graph = []

for _ in range(n):
    graph.append(list(sys.stdin.readline().strip()))
    

count = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == '-' or graph[i][j] == '|':
            dfs(i, j)
            count += 1
print(count)

밑에 반복문을 보면 if문 조건문에서 1로 바뀌지 않았다면 1개의 타일로 카운트가 되지 않은 걸 확인 할 수 있으니 카운트가 되는 부분의 문제가 해결된다.

옆에 -- 가 연속으로 나왔을 경우의 카운트 부분은 생각했지만 위 아래는 머릿속에 잘 그려지지 않았는데 생각해보면 인덱스를 갖고 확인하는 거다 보니 -1 만 해주면 위 아래, 양 옆을 모두 확인 할 수 있다. 또한 조건문으로 계속 재귀호출을 해서 깊이 탐색을 진행한다.

한 하지 내가 착각했던 게 질문에서 2개의 나무판자라고 해서 2개마다 하나로 묶는다고 생각을 했다.

답을 확인해볼 때 1번 예제에서 출력은 4다.
이 말은 서로 다른 타일로 인해 끊기지 않는 한 하나의 나무 판자로 카운트 한다는 소리다.

문제 자체를 잘못 이해했다는 점과 그래프 개념을 제대로 이해하지 못 해서 문제를 못 풀었다.

시간 복잡도와 공간 복잡도

시간 복잡도:

  • dfs() 함수는 연결된 그래프의 모든 노드를 한 번씩 방문한다. 이 때, 각 노드를 방문할 때마다 그 노드와 연결된 다른 노드를 재귀적으로 방문하므로 각 노드당 상수 시간이 소요된다.
  • 그래프의 모든 노드에 대해 dfs() 함수를 호출하기 때문에 이러한 호출은 n x m 번 발생한다. 여기서 n은 행의 수이고, m은 열의 수다.

따라서 전체 코드의 시간 복잡도는 O(n * m)다.

공간 복잡도:

  • graph 리스트는 n행 m열의 그래프를 저장하는데 사용된다. 따라서 이 리스트의 크기는 n x m다.
  • 재귀 호출을 통해 DFS가 진행될 때, 호출 스택에 각 호출에 필요한 정보가 저장된다. DFS의 최대 재귀 깊이는 그래프에서 연결된 요소의 수에 따라 달라진다. 최악의 경우, 모든 요소가 연결되어 있다면 최대 재귀 깊이는 n x m이 될 수 있다. 따라서 재귀 호출 스택의 최대 크기는 O(n * m)다.
    따라서 전체 코드의 공간 복잡도는 O(n * m)다.

회고 과정

가장 큰 문제는 내가 아직 그래프 (좌표)로 문제를 해결하는 부분이 부족하다고 느꼈다.
양 옆으로 만나는 -- 그리고 위 아래에서 만나는 || 이러한 부분이 좀 어려웠다.
특히 조건문으로 어떻게 만들어 내야 하는지 머릿속에서 그려지지가 않았는데 다음부터는 무조건 내가 스스로 풀 수 있었으면 좋겠다.

위에 방식은 dfs라는 함수를 만들어서 처리를 한 건데 생각해보니까 그래프는 일단 반복문을 두 번 사용해야 한다. (가로 행 열)
무조건 시간 복잡도를 낮추기 위해 반복문을 한 번으로 끝낼 생각을 하다 보니 더 바보가 되었다.

왜냐하면 사실 생각해보면 시간 복잡도는 O(n x m) 인데 무식하게 반복문 두 번 쓰면 O(n^2) 로 단순하게 생각했다. 😑

이전에 그래프 문제를 푼 적이 있었는데도 이런 생각을 했던 걸 보면 이전에 내가 이해한 건 주먹구구식이었기 때문이지 않을까?
너무 열 받고 부끄러웠다 ㅜㅜ

그래프는 진도를 나가기 보다는 내일 이 문제를 다시 풀고 이 아래에 새로 회고를 달기로!

CS 공부랑 알고리즘 및 자료구조 공부를 더 탄탄히 해야겠다고 다짐했다.

댓글남기기

참고