[문제풀이] week03 코드 리뷰1

바닥장식

풀이 시간: X
문제 요약:

2차원 배열에서 타일의 개수를 구하는 문제
'-' 와 '|' 의 바닥 타일이 있고, 다른 종류의 타일일 경우 타일을 잘라서 붙어야 하기에 총 타일의 개수를 구하는 문제

접근방법

타일 종류가 2가지 있고 타일별로 이어져 있는지 체크 해야함.
일방적인 방향성을 가지고 있으므로 방향을 체크하며 방문-캐시에 저장으로 재 방문을 방지

이미지로 이해해보자!

입력값:
4 4
-||-
--||
|--|
||--

아래는 타일 개수 카운팅하는 일련의 과정을 그려봤다.

스압주의

코드를 보자!

import sys
#sys.stdin = open('input.txt','r')

def bfs_w(y,x):
    while 0 <= x < m and floor[y][x] == '-':        #가로로 방문
        visited[y][x] = True
        x+=1
    return 1

def bfs_h(y,x):
    while 0 <= y < n and floor[y][x] == '|':        #세로로로 방문
        visited[y][x] = True
        y+=1
    return 1
        
floor = []
cnt =0
n,m = map(int, sys.stdin.readline().split())
visited = [[False for _ in range(m)] for _ in range(n)]

for y in range(n):
    floor.append(list(sys.stdin.readline().strip())) 

for y in range(n):
    for x in range(m):                              #2중 for문으로 2차원 배열 전체 순회
        if visited[y][x] == False:                  #동일한 2차원 배열은 visited 배열에서 False면 아래 코드 수행
            if floor[y][x] == '-':                  # '-' 타일 이면 가로 순회
                cnt +=bfs_w(y,x)
            else:
                cnt+= bfs_h(y,x)                     # '|' 타일 이면 세로 순회
                        
print(cnt)