[백준] 16932 모양 만들기

문제

www.acmicpc.net/problem/16932

 

(미완) 예제 통과, 백준 런타임 에러

코드

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))
visit = [[0] * 1000 for _ in range(1000)]
count = 0
groupNum = 1
group = [0] * 1000002
dx = [-1, 1, 0, 0] # 상, 하, 좌, 우
dy = [0, 0, -1, 1]

def dfs(x, y):
    global count
    count += 1
    visit[x][y] = groupNum

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:  # 가장자리 벽 pass
            continue
        if graph[nx][ny] == 0:  # 0은 이동할 수 없기 때문에 pass
            continue
        if visit[nx][ny]: # 이미 방문했으면 pass
            continue
        dfs(nx, ny)


def main():
    ans = 0
    global count, groupNum, group
    for x in range(n):
        for y in range(m):
            if graph[x][y] and not visit[x][y]:
                count = 0
                dfs(x, y)
                group[groupNum] = count # 그룹 크기 저장
                groupNum += 1

    for x in range(n):
        for y in range(m):
            if graph[x][y] == 0:
                candi = 1 # 1로 바꿨을 때 만들어지는 모양의 크기
                s = set()
                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]

                    if nx < 0 or ny < 0 or nx >= n or ny >= m:  # 가장자리 벽 pass
                        continue
                    if visit[nx][ny] == 0:
                        continue
                    if visit[nx][ny] in s:
                        continue
                    s.add(visit[nx][ny])
                    candi += group[visit[nx][ny]]

                ans = max(ans, candi)
    print(ans)

main()

 

풀이

1. graph의 값이 1인 원소들을 그룹화 시켜 넘버링 한 후 크기를 저장한다.
2. graph의 값이 0인 원소들을 1로 바꿔보고 0인 원소를 기준으로 상하좌우를 확인해 1인 모양의 그룹이 있는지 확인한다.
   1. 1인 모양의 그룹이 있다면, 그룹의 크기를 더한 후 0 ->1 을 변경했을 때 만들 수 있는 모양의 크기를 구한다.
3. ans 변수에 최댓값을 담아 갱신한다.