💡 문제
N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.
1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.
배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.
입력
첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.
출력
첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.
💭 접근
처음 이 문제를 풀었을 때는 아래의 처음 작성한 코드에서 볼 수 있듯이, 입력으로 주어진 graph가 1인 지점에서 인접한 네 지점을 1로 바꾼 뒤, BFS를 통해 인접한 모든 1의 개수를 구하는 방식으로 구현하였었다.
그러나 이러한 풀이에는 문제가 있었는데, 1이 있는 지점마다 최대 4번씩 계속해서 BFS 함수를 호출하게되어 시간초과가 발생한다는 것이었다. 이는 이미 확인했던 지점도 계속 반복해서 확인하기 때문이다.
이를 보완하기 위해 다른 방법을 사용하였다.
- 먼저 입력으로 주어진
graph에 1이 인접해 있는 것들끼리 그룹을 묶어주고, 크기를 저장한다.
idx = 1
for i in range(n):
for j in range(m):
if graph[i][j] == 1 and visited[i][j] == 0:
cnt = 1
tmp = [[i, j]]
bfs(i, j)
for x, y in tmp:
graph[x][y] = cnt
idx += 1위 코드를 그림으로 설명하면 다음과 같이 나타낼 수 있다.
먼저 입력으로 주어진 graph에 인접한 1끼리 그룹으로 묶어 그룹의 크기를 저장해준다.
그리고 visited에는 각 그룹의 번호(1 ~ n)를 저장해준다.
- 이후 1번 단계에서 만든 그룹들의 정보를 활용하여 값이 0인 임의의 지점에서 인접한 그룹들의 크기를 더하여 정답을 구한다.
ans = 0
for x in range(n):
for y in range(m):
if graph[x][y] == 0:
cnt = 1
idx_set = set()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] not in idx_set:
cnt += graph[nx][ny]
idx_set.add(visited[nx][ny])
ans = max(ans, cnt)위 코드를 그림으로 나타내면 아래와 같다.
이처럼 현재 [0, 2] 위치의 0이 선택되었다면, 인접하고 있는 서로 다른 그룹들의 크기를 더하여 인접한 1의 개수를 구할 수 있다.
🔥 처음 작성한 코드 (시간초과)
from collections import deque
def bfs(x, y):
q = deque()
q.append([x, y])
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[x][y] = 1
cnt = 1
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1
cnt += 1
q.append([nx, ny])
return cnt
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
pos = []
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
pos.append([i, j])
ans = 0
checked = [[0 for _ in range(m)] for _ in range(n)]
for x, y in pos:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and checked[nx][ny] == 0:
checked[nx][ny] = 1
graph[nx][ny] = 1
ans = max(ans, bfs(nx, ny))
graph[nx][ny] = 0
print(ans)📒 코드
from collections import deque
def bfs(x, y):
global cnt
q = deque()
q.append([x, y])
visited[x][y] = idx
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if graph[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = idx
q.append([nx, ny])
tmp.append([nx, ny])
cnt += 1
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
idx = 1 # 그룹 정보 저장
for i in range(n):
for j in range(m):
if graph[i][j] == 1 and visited[i][j] == 0:
cnt = 1
tmp = [[i, j]]
bfs(i, j)
for x, y in tmp:
graph[x][y] = cnt
idx += 1
ans = 0 # 정답 구하기
for x in range(n):
for y in range(m):
if graph[x][y] == 0:
cnt = 1
idx_set = set()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] not in idx_set:
cnt += graph[nx][ny]
idx_set.add(visited[nx][ny])
ans = max(ans, cnt)
print(ans)💭 후기
이전에 지도 상의 섬에 번호를 매기고 이들을 연결하는 비슷한 문제를 풀었던 기억이 떠올라 생각보다 쉽게 아이디어를 떠올릴 수 있었다.
🔗 문제 출처
https://www.acmicpc.net/problem/16932
