"""
https://www.acmicpc.net/problem/1012
유기농 배추
난이도: 실버 2 (체감: 중상. 공부하기 좋은 난이도)
시작: 21.05.26 19:47
끝: 21.05.26 21:22
성공: correct
메모리: 29200 KB
시간: 84 ms
[아이디어]
오른쪽, 아래쪽
재귀
한번 체크한 곳은 -1로 체크
[시간복잡도]
음,,, n개를 전부 훑어야 하므로 O(n)
[실수]
꺾인 ㄴ 모양이면 왼쪽으로 가는 것도 체크해줘야 한다!!
[0, 1, 0]
[1, 1, 0]
[0, 0, 0]
(x, y) = (1, 0) 도착
[0, 2, 0]
[1, 1, 0]
[0, 0, 0]
(x, y) = (1, 1) 도착
[0, 2, 0]
[1, 2, 0]
[0, 0, 0]
count증가 : 1
(x, y) = (0, 1) 도착
[0, 2, 0]
[2, 2, 0]
[0, 0, 0]
count증가 : 2
U 모양도 반례이다.
즉, 오른쪽, 아래, 왼쪽, 위 모두 체크 해야 한다
# 실수: result가 int이면 조인이 안 된다.
# solve()가 str을 리턴하게 했다.
[검색]
- 함수 파라미터: mutable 객체는 call by reference처럼 된다
- 재귀함수를 스택으로 만들기
https://comdoc.tistory.com/entry/10-스택과-재귀recursive-파이썬
[개선/추가사항]
처음에는 arr를 오른쪽, 아래쪽으로 하나씩 훑어 나가므로 재귀로 같은 영역인지 확인할 때도 오른쪽, 아래만 확인하면 된다고 생각했다.
히지만 ㄹ 모양이나 U 모양 등의 반례가 존재한다.
추후 비슷한 문제를 만나면 ㄹ 모양처럼 복잡한 모양의 예도 적용되는지 생각해봐야겠다.
(아님 일단 문제를 푸는 것이 중요하니 상하좌우 다 돌게 만들거나..)
내 풀이 중 find를 쓰는 풀이는 왜 RecursionError가 생기는지 모르겠다.
[고수풀이]
링크: https://www.acmicpc.net/source/14558062
메모리: 30048 KB
시간: 64 ms
접근법:
나랑 같다.
배울 점:
if o+1 < x and t[s][o+1]==1:
T(t,o+1,s)
이런 식으로 재귀함수에 들어간 다음 아니면 리턴하지 말고,
되는 경우에만 재귀 함수에 들어가도록 해봐야겠다.
아 근데 나랑 접근법은 같은데 왜 내가 재귀함수 썼을 때는 RecursionError가 난 걸까..
코드
import sys;p=sys.stdin.readline;
sys.setrecursionlimit(1000000)
q=int(p())
def T(t, o, s):
t[s][o]=0
if o+1 < x and t[s][o+1]==1:
T(t,o+1,s)
if o-1>= 0 and t[s][o-1]==1:
T(t, o-1,s)
if s -1 >= 0 and t[s-1][o]==1:
T(t, o,s-1)
if s +1 < y and t[s+1][o]==1:
T(t,o,s+1)
for _ in range(q):
x, y, c = map(int, p().split())
t = [[0] * x for _ in range(y)]
for i in range(0,c):
m,n=map(int,p().split());t[n][m] = 1
v = 0
for i in range(0,x):
for j in range(0, y):
if t[j][i] == 1:
T(t, i, j);v+=1
print(v)
"""
import sys
input = sys.stdin.readline
def solve() -> str:
M, N, K = map(int, input().split())
arr = [[0] * (M+2) for _ in range(N+2)]
for _ in range(K):
X, Y = map(int, input().split())
arr[Y+1][X+1] = 1
count = 0
for y in range (1, N+1):
for x in range(1, M+1):
if arr[y][x] == 1:
find4(arr, y, x)
count += 1
return str(count)
def find(arr: list, y: int, x: int):
if arr[y][x] == 2 or arr[y][x] == 0:
return
else:
arr[y][x] = 2
find(arr, y, x+1)
find(arr, y+1, x)
find(arr, y, x-1)
find(arr, y-1, x)
def find4(arr: list, y: int, x: int):
arr[y][x] = 2
if (arr[y][x+1] == 1):
find(arr, y, x+1)
if (arr[y+1][x] == 1):
find(arr, y+1, x)
if (arr[y][x-1] == 1):
find(arr, y, x-1)
if (arr[y-1][x] == 1):
find(arr, y-1, x)
def find2(arr: list, y: int, x: int):
stack = []
next = [[0, 1], [1, 0], [0, -1], [-1, 0]]
arr[y][x] = 2
stack.append([y, x])
while stack:
n, m = stack.pop()
for j, i in next:
yy = n+j
xx = m+i
if arr[yy][xx] == 1:
arr[yy][xx] = 2
stack.append([yy, xx])
def solve2() -> str:
M, N, K = map(int, input().split())
arr = [[0] * (M+2) for _ in range(N+2)]
for _ in range(K):
X, Y = map(int, input().split())
arr[Y+1][X+1] = 1
count = 0
print("\n".join(map(str, arr)))
for y in range (1, N+1):
for x in range(1, M+1):
if arr[y][x] == 1:
count += find3(arr, y, x)
print(f"count: {count}")
return str(count)
def find3(arr: list, y: int, x: int) -> int:
stack = []
next = [[0, 1], [1, 0]]
arr[y][x] = 2
stack.append([y, x])
while stack:
n, m = stack.pop()
arr[n][m] = 2
print(f"\n (x, y) = ({x}, {y}) 도착")
print("\n".join(map(str, arr)))
for j, i in next:
yy = n+j
xx = m+i
if arr[yy][xx] == 1:
arr[yy][xx] = 3
stack.append([yy, xx])
if arr[yy][xx] == 2:
print(f"\n (x, y) = ({x}, {y}) 이미 연결된 덩어리")
return 0
print(f"\n (x, y) = ({x}, {y}) 갈 곳 체크")
print("\n".join(map(str, arr)))
return 1
T = int(input())
result = [0] * T
for i in range(T):
result[i] = solve()
sys.setrecursionlimit(10**7)
print('\n'.join(result))