[백준] 5547 일루미네이션

문제

• 회색은 건물의 위치이고 흰색은 건물이 없는 곳이다. 
• 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식하려고 한다.
• 벽의 총 길이는 64미터이다.

 

• 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램 작성하기
• 1 <= W, H <= 100

 

풀이

• 짝수줄인지 홀수줄인지에 따라 바깥에 드러나는 벽면의 개수가 달라지므로 유의해야 한다!

1) 가장 바깥쪽 윗줄과 아랫줄의 경우,

• 0인 칸(건물이 없는 칸)이라면 주변에 인접한 1인 칸(건물이 있는 칸) 만큼 벽이 있어야 하고 

• 1인 칸(건물이 있는 칸)이라면 아무와도 인접하지 않지만 바깥에 돌출된 만큼 추가의 벽이 있어야 한다.
  -> 위에 돌출된 삿갓같은 2개 

 

 

2) 가장 왼쪽 줄과 오른쪽 줄의 경우

• 0인 칸이라면 주변에 인접한 1인 칸 만큼 벽이 있어야 하고
• 1인 칸이라면 왼쪽줄의 짝수칸 + 오른쪽 줄의 홀수칸은 3개, 왼쪽줄의 홀수칸 + 오른쪽 줄의 짝수칸은 1개가 필요하다.

 

 

• 여기서 왼쪽줄의 짝수칸 + 오른쪽 줄의 홀수칸이면서 제일 윗줄과 마지막줄에 해당하는 경우 삿갓이 하나씩 겹치므로, 제거해주도록 한다.

 

 

d = [
    [(-1, 0), (-1,1), (0,-1), (0,1), (1,0), (1,1)],
    [(-1, 0), (-1, -1), (0, -1), (0, 1), (1, 0), (1, -1)]
]

# 테두리 개수 반환
def dfs(y, x) :
    s = [(y, x)]
    visited[y][x] = 1
    cnt = 0
    while s :
        y, x = s.pop()
        for dy, dx in d[y%2] :
            ny, nx = y+dy, x+dx
            if 0 <= ny < H and 0 <= nx < W and not visited[ny][nx] :
                if graph[ny][nx] : 
                    cnt += 1
                else :
                    visited[ny][nx] = 1
                    s.append((ny, nx))
    return cnt

# 입력 받기
W, H = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(H)]
visited = [[0]*W for _ in range(H)] # 방문 배열

# 벽면 찾기
wall = 0
## 가장 바깥쪽 윗줄, 아랫줄 탐색
for y in [0, H-1] : 
    for x in range(W) :
        if graph[y][x] :
            wall += 2           # 위에 삿갓
            if (y==0 and x==W-1) or (y==W-1 and x==0) :
                wall -= 1       # 마지막 칸에 겹치는 하나 제외
        elif not visited[y][x] :
            wall += dfs(y, x)   # 인접한 칸의 개수 = 바깥 벽면 개수

## 가장 바깥쪽 왼쪽줄, 오른쪽줄 탐색
for y in range(H) :
    for x in [0, W-1] :
        if graph[y][x] :
            if (x==0 and y%2) or (x==W-1 and y%2==0) :
                wall += 3       # 벽면이 세개
            else :
                wall += 1       # 벽면이 하나
        elif not visited[y][x] :
            wall += dfs(y, x)   # 인접한 칸의 개수 = 바깥 벽면 개수

print(wall)

 

References

• 백준 그래프탐색