[python] 백준 1012 : 유기농 배추
2차원 배열 문제입니다. 표에서 1의 군집을 찾으면 되는데요. 군집 검사시에는 상하좌우로 한칸씩, 대각선은 검사하지 않습니다. 어.. 사실 좀 어려웠습니다. 일단 2차원 배열의 생성부터, 자유롭게 그 안에서 이동하며 검사하는게 어렵더군요.
정석대로라면 0으로 채워진 2차원 배열에 입력받은 위치에만 1을 더해 상하좌우 검색하며 군집갯수를 파악하면 되는데..
저는 생각했습니다. "배열을 다루기 어려우면 배열을 안쓰면되는거아님?" 아 물론 알고리즘 문제에서 2차원배열에 관한 문제는 자주나오기때문에 파이썬기준 numpy를 쓸때, numpy를 쓰지않을때 배열 다루는법 모두 알고있으면 무적권 유리할거같습니다. (저는 코딩 응애여서 배열하면 무조건 넘파이(numpy)부터 생각하는데.. 이번 문제를보고 깨달아버렸읍니다.. 나중에 넘파이 사용법을 적은 비법(아무도 안궁금함)글도 한번 올려보겠습니다.)
일단 배열을 쓰지 않는 방향으로 먼저 해보겠습니다. 논리구조를 생각해봅시다.
배추의 위치 x,y를 입력받습니다. 이때 이 x,y를 저장할 리스트 x_list, y_list를 각각 만들어 입력받는 족족 리스트에 저장해줍시다. 예를들어 입력받은 배추의 위치값이 (0,0),(1,0),(2,4)라면 x_list = [0,1,2] y_list = [0,0,4]로 저장이 되겠지요.
이제 이 리스트안에서 검사를 진행해보면됩니다. 각 리스트의 i번째 요소에 대해 상하좌우로 1씩 더했을때의 값이 존재하고(리스트 안에 있고) x,y리스트의 인덱스가 같다면 인접한 배추가 있는것이죠.
예를들어. x_list[i]와 y_list[i]에 대해 윗방향으로 1을 더했을때 (x+0, y+1)나온값이 (3,2)라고 칩시다. 이때 배추의 위치 리스트인 x_list와 y_list안에 이 값이 있는지를 파악하는것도 중요하지만, 이 둘은 (3,2)의 관계로, '같은 인덱스값'을 가져야합니다. x_list=[1,3,2] y_list=[4,5,2]라면 좌표상으론 (1,4),(3,5),(2,2)지만, 유무검사를 했을땐 어쨌든 각 리스트에 숫자 3,2가 존재하므로 True로 출력됩니다. 이런상황을 방지하기위해 인덱스 일치 조건은 필수적입니다.
만약 존재한다면 그 위치로 옮겨가서 거기에서 다시 검사를 진행해야죠. 여기서 약간 느낌이 오시겠지만,
if True시에 앞에서 진행한 검사를 위치를 옮겨서 다시한다? 이거 어디서 본 구조죠?
바로 재귀호출이 필요한 구조입니다. (옛날에 팩토리얼의 기억을 되살려봅시다...) 재귀문으로 계속 꼬꼬무식 검사를 해주면 됩니다.
def organic_bachu(x,y):
dx=[0,0,1,-1]
dy=[1,-1,0,0]
br = False
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx in x_list and ny in y_list and x_list.index(nx)==y_list.index(ny):
y==-1 and x==-1 and organic_bachu(nx,ny)
br = True
break
elif nx<0 or ny<0 or nx>m or ny>n:
continue
if not br:
warm_list.append('w')
T=int(input())
for _ in range(T):
m,n,k = map(int,input().split())
x_list=[]
y_list=[]
warm_list=[]
for _ in range(k):
x,y = map(int,input().split())
x_list.append(x)
y_list.append(y)
for j in range (len(x_list)):
organic_bachu(x_list[j],y_list[j])
print(len(warm_list))위의 논리구조를 구현해본 코드인데.... 문제가 있네요,,,
예제값과 다른값이 나옵니다.. 제출할수도 없는 코드가 나와버림
코드를 설명해보자면 dx와 dy를 이용해 4방향 탐색을 해줍니다. 만약 4방향 탐색중 if문에 걸리지않으면 아무런 동작도 수행하지 않습니다. 만약 이상치조건 (nx<0, nx>m등...)에 걸리면 없던걸로 하구요. 그러다 if문에 걸려버리면 재귀호출을 합니다. 재귀호출을 하는데 기존에 x,y는 -1로 바꿔버려서 다음 호출시 이상치조건에 걸리게합니다. 또한 아래 br=True를 할당해줍니다. br의 기능은, br = False로 시작해 4방향 탐색을 할때, 4방향중 한곳이라도 인접한 배추가 있다면 그 위치에선 시행을 종료해야하고, 해당 반복문 자체를 그냥 True로 할당해버려 경우의 수에 더하지않습니다. 계속 꼬꼬무 탐색하다가 마지막에 끝 탐색에서 결국 4방향 탐색 실패해서 False로 출력되겠죠. 그때 가장 마지막 조건에 걸려서 warm_list에 한마리 추가되는 의도로.. 짜봤습니다만 ....아쉽게됐네요 그래도 열심히하시잖아~
어.. 일단 차근히 해결해보는걸로 하고 어차피 배열을 이용한 풀이도 하려했으니 그거먼저 합시다.
배열을 사용한다면 입력받은 m,n크기만큼의 zeros배열을 생성한후 입력받은 배추의 위치에 1을 더해줍니다.
탐색시에는 똑같은 방식으로 재귀호출을 하되 위에서 애먹은 중복과 종료조건을 여기선 좀더 쉽게 쓸수있습니다. 바로 재귀호출시 이전에 있던 배추의 위치엔 다시 0을 할당해주는거죠. 함수는 4방향 탐색을했을때 배추가없다면 0을 반환, 배추가 있다면 재귀호출을 합니다. 이걸 반복하다 한 군집에 대해 검사가 끝나면 1을 반환하는거죠.
T = int(input())
for _ in range(T):
m, n, k = map(int, input().split())
matrix = [[0] * m for _ in range(n)]
for _ in range(k):
x, y = map(int, input().split())
matrix[x][y] = 1
print(matrix)영배열 (영행렬..은 아는데 영배열은.. 그냥 제가 지어낸말입니다. 대충 0으로 찬 배열이란뜻 ㅎ)을 생성해서 직접 확인해봅시다. [[0]*m for _ in range(n)] 에서 배열을 생성합니다. 되게 직관적이죠?
배열을 눈으로 봅시다. 5x3크기 배열에 (1,1) (2,2)위치에 배추가 있다면 저런식으로 출력됩니다. 우리가 아는 2차원 배열의 모양이랑 다르죠? 그래도 계산상으론 2차원으로 계산됩니다. 왜냐하면 괄호 [ 가 두겹으로 되어있기 때문입니다.
파이썬에서 [2,2]는 1차원 배열이구요, [[2,2]]는 2차원배열입니다. 그렇다면 [[[2,2]]]은? 3차원 배열이 되겠죠. 괄호의 갯수로도 판단할수있습니다. 암튼 이런식으로 배열을 생성해 배열안에 배추를 입력해줄수 있습니다.
def organic_bachu(x, y):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
if x < 0 or y < 0 or x >= m or y >= n:
return 0
if matrix[x][y] == 0:
return 0
matrix[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if matrix[nx][ny] == 1:
organic_bachu(nx, ny)
return 1함수부분입니다. 4방향 탐색하는것은 위와 동일하지만 조건과 반환값이 다르죠.
첫 if문에선 조건에 맞지않는 값들에 대한 처리, 두번째 if문에선 배추가 없는 부분에 대한 처리입니다. 둘다 0을 반환합니다. 그러다 두 if문을 다 통과하는, 배추가 있는 자리라면 if문 통과후 해당지역은 matrix[x][y]에 걸려 0으로 바뀝니다. 이 부분은 중복을 방지하기 위해 거치는 단계입니다. 이후 for문에 들어가 배추가 있는 지점에 대해서 4방향 탐색이 시작됩니다. 그리고 만약 4방향에서 1인 지점이 발견되면 재귀호출에 들어갑니다.
재귀호출이 다끝난다면 마지막으로 1을 반환하는거죠. 이게 한개의 배추군집입니다.
import sys
sys.setrecursionlimit(10000)
def organic_bachu(x, y):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
if x < 0 or y < 0 or x >= m or y >= n:
return 0
if matrix[x][y] == 0:
return 0
matrix[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if matrix[nx][ny]==1:
organic_bachu(nx, ny)
return 1
T = int(input())
for _ in range(T):
m, n, k = map(int, input().split())
matrix = [[0] * m for _ in range(n)]
for _ in range(k):
x, y = map(int, input().split())
matrix[x][y] = 1
cnt = 0
for i in range(m):
for j in range(n):
cnt += organic_bachu(i, j)
print(cnt)위아래로 합친 전체코드입니다. mxn짜리 전체 영역에 대해 1이 얼마나 반환되나 갯수를 세면 됩니다.
위에 sys.setrecursionlimit는 재귀호출로 인해 계산과정이 무한히 길어지는것을 방지하기위해 제한값을 설정하는겁니다
만약 이걸 설정안한다면...
요래됩니다! 런타임 에러는 아마 무한츠쿠요미 재귀호출땜에 뜨는것같네요.....
실버 2티어 문제인데.. 체감난이도는 꽤나 높았네요.. 아마 탐색 알고리즘 문제에 대한 경험이 없고 함수 동작에서 얼타서 시간이 많이걸리고 중간에 틀리기도했던것 같습니다. 어쩌다보니 이번 방학때 부트캠프 수강할수있는 좋은 기회가 생겼는데 좀더 강해져서 돌아오겠읍니다. 아 물론 부트캠프 들으면서 글도 쓸거에요
처음에 말한 '틀린 알고리즘'도 버리기 아까워서 일단 기록해두고 고쳐나가보겠읍니다. (솔직히 올해안에 다시 손댈까 의문이긴함 ㅋㅋ) 그래도 열심히하시잖아~