문제
https://www.acmicpc.net/problem/16234
접근
BFS를 통해 풀이가 가능한 문제이다.
Python3로는 통과 못하고 PyPy3로 통과했다.
문제 풀기전에 손으로 수도코드 어느정도 작성하고 시작하는게 확실히 도움이 되는 것 같다.
처음에 Union-Find 자료구조를 이용할까 하다가 그냥 BFS 돌면서 한 집합에 모으기만 하면 될 것 같아 이용하지 않았다.
소스 코드
from collections import deque
import sys
input = sys.stdin.readline # 시간초과 방지용
dx = [0,0,-1,1]
dy = [1,-1,0,0]
def is_valid(x,y,N):
if 0<=x<N and 0<=y<N:
return True
return False
def bfs(x ,y, is_visited, L,R, A):
union = {(x,y)}
queue = deque([[x,y]])
is_visited[x][y] = True
while queue:
x,y = queue.popleft()
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if is_valid(new_x, new_y, N) and not is_visited[new_x][new_y] and L<=abs(A[x][y]-A[new_x][new_y])<=R:
union.add((new_x,new_y))
queue.append((new_x, new_y))
is_visited[new_x][new_y] = True
return union
N,L,R = map(int, input().split())
A = [list(map(int,input().split())) for _ in range(N)]
answer = 0
find_union = True
while(find_union):
find_union = False
is_visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not is_visited[i][j]:
union = bfs(i,j,is_visited, L,R, A)
if len(union) >=2: # 2개 이상 지역이 연합
find_union = True
# 인구 갱신
change_population = int(sum(A[x][y] for x,y in union) / len(union)) # 버림
for x, y in union:
A[x][y] = change_population
if find_union: # 인구이동 일어났으면(한턴에 여러번 발생하는 것도 하나로 처리해야함)
answer += 1
print(answer)개선점
- while문에서 while True로 두고, 조건을 만족 안할 때 break시키는게 좀 더 깔끔한거 같다.
while True:
find_union = False
<로직>
if not find_union:
break- 전역에서 선언된 변수 굳이 파라미터로 넣지말고 바로 접근하자.
# def bfs(x ,y, is_visited, L,R, A)
def bfs(x ,y, is_visited):
pass
N,L,R = map(int, input().split())
A = [list(map(int,input().split())) for _ in range(N)]프로그래머스처럼 함수 내에 구현하게 나온 경우 그 안에 함수를 구현하자.(중첩함수)
주의) 재할당(=)이 일어날 경우 참조 ID가 변경되어 별도의 로컬 변수로 선언되므로 주의가 필요하다. 즉, 재할당된 값은 부모 함수에서는 반영X
def solution(n):
def bfs(x ,y, is_visited):
pass
N,L,R = map(int, input().split())
A = [list(map(int,input().split())) for _ in range(N)]Github
성장!