[python/백준] 1388. 바닥 장식(S4)

📌 문제 탐색하기

👉 문제바로가기
N, M: 방 바닥의 세로 크기, 가로 크기(N, M은 50이하의 자연수)

행과 열이 있는 값을 입력받아야하므로 2차원 리스트로 접근할 수 있습니다.

방문한 노드의 값이 -이면 오른쪽으로 이동하면서 아직 방문하지 않은 노드 중 값이 -이면 계속해서 탐색합니다. 방문한 노드의 값이 |이면 세로로 이동하면서 아직 방문하지 않은 노드 중 값이 |일때까지 탐색하면되는 문제입니다.

📌 알고리즘 선택

DFS(Depth-First Search)

DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 어떤 한 시작 지점이 있다면 가로 혹은 세로로 모두 탐색을 끝낸 후 다른 곳을 탐색해야 하고, 모든 경우를 하나하나 전부 탐색해야하기 때문에 DFS알고리즘을 선택했습니다.

시간복잡도

하나의 정점에서 탐색하는 경우 시간복잡도는 O(N)또는 O(M)입니다. 정점이 될 수잇는 경우는 N*M이므로 모든 행과 열을 탐색하는 시간복잡도는 O(N*M)*(O(N) 또는 O(M))이 됩니다. N, M의 최댓값은 50이므로 최악의 경우 50*50*50 = 125,000회의 연산이 필요합니다. 이는 주어진 시간 내에 충분히 가능한 연산 횟수입니다.

📌 코드 설계하기

1. N(세로), M(가로)를 Input받습니다.
2. 입력받은 N, M의 크기에 맞게 -또는 |를 Input받아 2차원 리스트에 저장합니다.
3. 방문 여부를 N, M의 크기와 동일한 리스트로 저장합니다. (탐색 시점 이전에는 모두 방문하지 않았으므로 False로 초기화합니다.)
4. 그래프를 모두 탐색하면서 dfs알고리즘을 실행합니다.

📌 정답 코드

import sys

def dfs(x, y):
    visited[x][y] = True
    if graph[x][y] == '|':
        if x + 1 < N and visited[x+1][y] == False and graph[x+1][y] == '|':
            dfs(x+1, y)
        else:
            return
    if graph[x][y] == '-':
        if y + 1 < M and visited[x][y+1] == False and graph[x][y+1] == '-':
            dfs(x, y+1)
        else:
            return             
    

N, M = map(int, sys.stdin.readline().split())  #N(세로), M(가로)
graph = []  #타일 리스트
count = 0   #타일 갯수
visited = []   
arr = [False]*M  #특정 행의 방문 여부

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

for _ in range(N):
    visited.append(arr[:])

for i in range(N):
    for j in range(M):
        if visited[i][j] == False:
            dfs(i, j)
            count+=1
            
print(count)