[CodeTree/Python] 정육각형으로 이루어진 배열

문제

요아정에 벌집 추가

이거 실버 문제인거 진짜 구라같다 말도안됨

정육각형으로 이루어진 배열

정육각형의 형태로 이루어진 n x m 크기의 배열의 각 칸에 0 또는 1의 값이 주어져 있습니다.

각 정육면체는 다음과 같이 이어져 있습니다. 색칠된 칸은 1의 값이 주어져 있는 칸입니다.

1이 적힌 정육각형 칸들로 이루어진 집합의 겉을 둘러싸는 벽의 길이의 합을 구하는 프로그램을 작성해보세요. 정육각형의 한 변의 길이는 1 입니다.

아래 그림에서는 붉은 선으로 표시된 부분이 겉을 둘러싸는 벽의 영역입니다.

 

입력 형식

첫 번째 줄에 정수 n과 m이 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 m개씩 1 또는 0이 주어집니다.

• 1 ≤ n, m ≤ 100

출력 형식

1이 적힌 정육각형 칸들로 이루어진 집합의 겉을 둘러싸는 벽의 길이를 모두 더한 값을 출력합니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

해결

1. 실패 시도들

    풀이하기로 한 DFS 문제에서 가장 어려웠던 문제(ㅠㅠ) 처음에는 1로 주어지는 값을 기준으로 DFS를 돌렸다.

• 맵 위에서 6방향 인접 노드 좌표를 정해줘야 하고, DFS를 돌면서 인접 노드의 값을 확인해야 한다.
  * 정육각형이 벌집 모양으로 지그재그로 붙어있기 때문에, 6방향 인접 노드의 좌표는 짝수행인지, 홀수행인지에 따라 다르다.
• 인접 노드를 탐색하면서, 2가지를 고려한다.
  
  1. 인접 노드가 맵의 범위에서 벗어나는 경우: 탐색 노드가 가장 겉다리에 있는 노드이므로 카운트를 추가한다.
  2. 인접 노드의 값이 0인 경우, 카운트를 추가한다.
     인접 노드의 값이 1이고 아직 방문하지 않은 노드인 경우, 재귀 함수를 통해 이동하여 방문 처리 후 계속 탐색한다.

"""
6방향 인접칸 구하기
(2,3)일 때
(x - 1, y - 1)
(x - 1, y)
(x, y - 1)
(x, y + 1)
(x + 1, y - 1)
(x + 1, y)

(3,3)일 때
(x - 1, y)
(x - 1, y + 1)
(x, y - 1)
(x, y + 1)
(x + 1, y)
(x + 1, y + 1)
"""
n, m = map(int, input().split())
# 2차원 리스트 맵 생성
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# 방문 처리를 위한 리스트 생성
visit = []
for i in range(n):
    visit.append([False] * m)

# 2차원 맵 내에서의 재귀함수 생성
def dfs(x, y):
    # 현재 노드가 1이고, 해당 노드를 방문하지 않았을 시 방문 처리
    if graph[x][y] == 1 and visit[x][y] == False:
        visit[x][y] = True
        count = 0
        # 각 인접칸의 방향 정의 -> 짝수행인 경우, 홀수행인 경우
        if x % 2 == 0:
            directions = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)]
        else:
            directions = [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, 0), (1, 1)]
        
        for dx, dy in directions:
            # 현재 노드의 인접칸 좌표를 설정하고, 하나씩 반복문 돌며 확인
            nx, ny = x + dx, y + dy 
            # 인접 노드의 값이 0이거나 범위를 벗어나는 경우, 벽의 개수 카운트 증가
            # 범위를 벗어나는 경우, 값을 가지지 않으므로(index를 벗어나는 값) 해당 경우 조건을 먼저 처리
            if nx <= -1 or nx >= n or ny <= -1 or ny >= m or graph[nx][ny] == 0:
                count += 1
            # 인접 노드가 방문하지 않은 노드인 경우, dfs를 재귀적으로 돌며 위 반복문에 대한 카운트 추가
            # dfs 탐색
            elif graph[nx][ny] == 1 and visit[nx][ny] == False:
                count += dfs(nx, ny)
        return count
    return False

ans = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and visit[i][j] == False:
            ans += dfs(i, j)

print(ans)

 

    해당 코드에서 문제가 있었다.

반복문으로 첫 칸부터 끝까지 탐색을 돌리다 보니, 곧 죽어도 1로 둘러싸인 내부 칸에 대한 카운트를 한다는 거다. 

    for ax, ay in dir:
    	mx, my = nx + ax, ny + ay # 인접 노드의 인접 노드...
        if mx <= -1 or mx >= n or my <= -1 or my >= m:
        	continue # 위 노드가 범위를 벗어날 경우, continue
        arr.append(graph[mx][my])
    print(arr)
    if arr = [1,1,1,1,1,1]:
    	continue
    count += 1

 

    인접 노드의 인접 노드까지 세보고 별 짓을 다 했다 인접 노드가 감싸져 있는 노드의 경우, 인접 노드의 인접 노드들은 전부 1일 거라는 가정을 하고 리스트를 만들어 확인했는데, 제대로 안 나왔다. 패스

 

2-1. 재귀 함수를 사용하여 풀이

    결국 여기저기 검색하다가, [백준 5547] 일루미네이션 문제와 같은 문제란 걸 알았다. 재귀 함수를 생성하는 코드는 나랑 짜는 방법이 다른 것 같아서, 풀이 아이디어만 가져왔다. 1 말고 0을 기준으로 DFS 돌리는 방법? 상상도 못한 정체

• 입력값으로 주어진 맵에서 상하좌우로 육각형을 하나씩 더 추가하여 맵을 확장한다.
  * 맵의 바깥 부분을 모두 확장하므로, 내부에 존재하는 칸을 제외하고 0인 모든 칸이 연결된다.
• 겉다리에 있는 아무 칸이나 잡고, DFS로 인접 노드를 탐색하며 카운트한다.
• 인접 노드를 탐색하면서, 다음을 고려한다.
  1. 인접 노드가 맵의 범위에서 벗어나는 경우, 1과 인접할 확률은 0이므로 고려하지 않는다.
  2. 인접 노드가 맵의 범위에 존재하는 경우: 인접 노드의 값이 1이라면 카운트한다.
  3. 인접 노드의 값이 0이고 아직 방문하지 않은 노드인 경우, 재귀 함수를 통해 이동하여 방문 처리 후 계속 탐색한다.

n, m = map(int, input().split())
# 2차원 리스트 맵 생성
graph = []
# 맵의 상하좌우에 0으로 둘러싸이도록 1칸씩 확장
graph.append([0] * (m+2))
for i in range(n):
    graph.append([0] + list(map(int, input().split())) + [0])
graph.append([0] * (m+2))

# 방문 처리를 위한 리스트 생성
visit = []
for i in range(n + 2):
    visit.append([False] * (m + 2))
count = 0

# 2차원 맵 내에서의 재귀함수 생성
def dfs(x, y):
    global count
    # 현재 노드가 0이고, 해당 노드를 방문하지 않았을 시 방문 처리
    if graph[x][y] == 0 and visit[x][y] == False:
        visit[x][y] = True
        # 각 인접칸의 방향 정의 -> 짝수행인 경우, 홀수행인 경우
        if x % 2 == 0:
            directions = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)]
        else:
            directions = [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, 0), (1, 1)]
        
        for dx, dy in directions:
            # 현재 노드의 인접칸 좌표를 설정하고, 하나씩 반복문 돌며 확인
            nx, ny = x + dx, y + dy 
            # 인접 노드가 맵의 범위 내에 있는 경우만 방문 처리를 확인한다.
            # 맵에서 1로 주어진 경우, 벽의 개수를 1개 추가한다.
            if (0 <= nx < n + 2) and (0 <= ny < m + 2):
                if graph[nx][ny] == 1:
                    count += 1
            # 인접 노드가 방문하지 않은 노드인 경우, 재귀적으로 돌며 dfs 탐색
                if graph[nx][ny] == 0 and visit[nx][ny] == False:
                    dfs(nx, ny)

# 내부의 빈 부분까지 확인할 필요는 없으므로, 시작점을 (0,0)으로 설정해 겉부분만 탐색
# 맵의 확장으로 인해 모든 칸이 연결되어 있다.
dfs(0,0)
print(count)

아잠만

 

    코드 실행 돌리고, 테스트 케이스 통과하길래 드디어 이 문제 탈출이구나 놀러가야지 룰루랄라 했는데 런타임 에러가 떴다.
아무래도 시간 제한이 1,000ms인데 재귀 함수가 너무 많이 돌아가서 그런가 결국 이 풀이도 스택으로 갈아 엎었다.

 

2-2. 스택을 사용하여 풀이

    고려 사항은 동일하고, 재귀 함수만 스택으로 변경했다. 그래도 틀이 동일해서 금방 바꿨다.
아까 검색할 때 보니까 백준에서 푼 사람들은 유형이 안 정해져 있어서 그런가 BFS로 푼 사람들이 많더라.

n, m = map(int, input().split())
# 2차원 리스트 맵 생성
graph = []
# 맵의 상하좌우에 0으로 둘러싸이도록 1칸씩 확장
graph.append([0] * (m+2))
for i in range(n):
    graph.append([0] + list(map(int, input().split())) + [0])
graph.append([0] * (m+2))

# 방문 처리를 위한 리스트 생성
visit = []
for i in range(n + 2):
    visit.append([False] * (m + 2))
count = 0

# 2차원 맵 내에서의 스택 생성
def dfs(x, y):
    global count
    stack = []
    stack.append((x, y))
    # 현재 노드가 0이고, 해당 노드를 방문하지 않았을 시 방문 처리
    if graph[x][y] == 0 and visit[x][y] == False:
        visit[x][y] = True
    
    while stack:
        x, y = stack.pop()
        # 각 인접칸의 방향 정의 -> 짝수행인 경우, 홀수행인 경우
        if x % 2 == 0:
            directions = [(-1, -1), (-1, 0), (0, -1), (0, 1), (1, -1), (1, 0)]
        else:
            directions = [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, 0), (1, 1)]
        
        for dx, dy in directions:
            # 현재 노드의 인접칸 좌표를 설정하고, 하나씩 반복문 돌며 확인
            nx, ny = x + dx, y + dy 
            # 인접 노드가 맵의 범위 내에 있는 경우만 방문 처리를 확인한다.
            # 맵에서 1로 주어진 경우, 벽의 개수를 1개 추가한다.
            if (0 <= nx < n + 2) and (0 <= ny < m + 2):
                if graph[nx][ny] == 1:
                    count += 1
            # 인접 노드가 방문하지 않은 노드인 경우, 스택에 추가하고 방문 처리
                if graph[nx][ny] == 0 and visit[nx][ny] == False:
                    stack.append((nx, ny))
                    visit[nx][ny] = True

# 내부의 빈 부분까지 확인할 필요는 없으므로, 시작점을 (0,0)으로 설정해 겉부분만 탐색
# 맵의 확장으로 인해 모든 칸이 연결되어 있다.
dfs(0,0)
print(count)

미친 것 다신 보지 말자