백준 알고리즘 1388

문제

예제

2개 이상의 -또는 |가 같은 방향으로 붙어있는 경우 하나의 나무 판자를 의미하며 이 나무 판자의 개수를 세어야 한다.

---

나의 시도

N, M = map(int, input().split())

floor = []
cnt = 0

gaflag = False
seflag = False

for i in range(N):
  pt = input()
  floor.append(list(pt))
#print(floor)

while floor:
  pt = floor.pop(0)
  for i in range(M):
    if gaflag == False:
      if pt[i] == '-':
        gaflag = True
      else:
        cnt += 1
        #print("ga", pt, i)
        gaflag = False
    elif pt[i] != '-':
      cnt += 1
      #print("ga", pt, i)
      gaflag = False

    if seflag == False:
      if pt[i] == '|':
        seflag = True
        seseat = i
    elif seflag == True and seseat == i:
      if pt[i] != '|':
        cnt += 1
        #print('se', pt, i)
        seflag = False

  if gaflag == True:
    cnt += 1
    gaflag = False
    #print("ga", pt, i)

  #print(pt, cnt)

print(cnt)

한 줄 씩 입력 받아 해당 내용을 list로 만들어 floor라는 빈 리스트 안에 넣어준다.
시간복잡도를 위해 while 문 안에 for문을 사용하는 구조로 짰으며 각 행의 열별로 무늬를 확인한 후 flag을 껐다 켰다 하며 개수를 세려고 하였다.

하지만 위 코드의 문제는

여기의 else문. gaflag이 꺼져 있고 다른 무늬면 카운트를 하기만 했다는 점이다.

또한 이 부분

이도 마지막에 다른 무늬인 걸 확인할 때 카운트가 올라가다보니 행 단위로 확인하다 보니 한 행에 두 개 이상의 세로 무늬가 있을 때 확인이 어렵다는 점이 문제였다.

사실 깊이 우선 탐색 문제라는 건 알았지만 깊이 우선 탐색 자체가 기억이... 잘 안 났기 때문에...

깊이 우선 탐색 >> 일단 노드에 인접한 노드 중 아직 방문하지 않은 노드를 스택에 저장해두고 꺼내면서 확인하는 것...

머리의 한계로 2시간 안에 문제를 못 풀었기 때문에(더 오래 걸리면 평생 못 풀고 다른 다양한 문제도 못 풀어볼 게 뻔해서) 다른 사람들의 모범 사례를 보고 학습해보도록 하겠습니다.

참고블로그
https://ye5ni.tistory.com/135

위 블로그에서 본 코드는 아래와 같다.

# dfs 알고리즘 함수 정의
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, input().split()) # 방 바닥의 세로 크기 n, 가로 크기 m
graph = []  # 2차원 리스트의 맵 정보 저장할 공간
for _ in range(n):
    graph.append(list(input()))
 
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)

재귀함수를 이용해 '-'무늬일 때와 '|'무늬일 때 확인해야 하는 위치(같은 방향 양 옆)을 잘 확인하고 탐색을 했다면 1로 바꿔주어 이중 for문으로 바닥 무늬를 확인했을 때 인접한 곳의 무늬를 확인해 적절하게 바닥 장식의 개수를 세어주는 코드이다.

---

내 코드의 경우 수업시간에 배운 스택을 이용해서 깊이 우선 탐색을 처리하는 방법 역시 생각하지 못 했고 그렇게 일일히 모든 조건을 고려해서 카운트를 하려고 하다보니 제대로 된 코드를 작성하지 못 했던 듯 하다. 해당 코드를 참고해 깊이 우선 탐색에 대해 이해하고 관련된 문제를 더 풀어보아야 할듯