acmicpc.net 2667(백트래킹), 1012(백트래킹)

https://www.acmicpc.net/problem/2667

이거 하나 푸느라 한참 고생했다. 

count = 1
def check(i,j):
    maps[i][j] = count
    if i-1>=0 and maps[i-1][j]=='1':
        check(i-1,j)
    if i+1<=n-1 and maps[i+1][j]=='1':
        check(i+1,j)
    if j-1>=0 and maps[i][j-1]=='1':
            check(i,j-1)
    if j+1<=n-1 and maps[i][j+1]=='1':
            check(i,j+1)

n = int(raw_input())
maps = [list(raw_input()) for i in range(n)]
for i in range(n):
    for j in range(n):
        if maps[i][j]=='1':
            check(i,j)
            count += 1
print count-1
s = [0 for i in range(count-1)]
for i in range(1,count):
    for j in range(len(maps)):
        for k in range(len(maps[j])):
            if maps[j][k]==i:
                s[i-1] += 1
#print maps
print '\n'.join(map(str,sorted(s)))

https://www.acmicpc.net/problem/1012

이건 예전에 풀다 포기한 유기농 배추 문제인데 백트래킹으로 푸는거였다. 그런데 파이썬에서는 코드가 더 필요했다.

아래 sys.setrecursion~이걸로 재귀 용량을 더 늘려줬는데, 이거 없으면 런타임 에러가 떠버린다. c로는 아래와 동일한 알고리즘을 써서 코드를 짜면 성공하는데 파이썬은 기본적으로 재귀가 c보다 적게 되서(라고 들었다.) 추가 옵션이 필요했다.

import sys
sys.setrecursionlimit(100000) #이거 꼭 필요한 코드!
def bug(i,j):
    global field
    field[i][j] = 0
    if i-1>=0 and field[i-1][j]==1: bug(i-1,j)
    if i+1<n and field[i+1][j]==1: bug(i+1,j)
    if j-1>=0 and field[i][j-1]==1: bug(i,j-1)
    if j+1<m and field[i][j+1]==1: bug(i,j+1)
t = int(raw_input())
bug_count = [0 for i in range(t)]
for i in range(t):
    m,n,k = map(int,raw_input().split())
    field = [[0 for b in range(m)] for a in range(n)]
    for j in range(k):
        x,y = map(int,raw_input().split())
        field[y][x] = 1
    #print '\n'.join(map(str,field))
    for a in range(n):
        for b in range(m):
            if field[a][b]==1:
                bug(a,b)
                bug_count[i] += 1
print '\n'.join(map(str,bug_count))