acmicpc.net 2638(BFS), acmicpc.net 2636(BFS)

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

치즈 문제. 중간에 주석 풀면 치즈가 어떻게 변해가는지 볼 수있다.

bfs()함수로는 0,0를 외부 공기의 시작점으로 보고 근처에 있는 공기들은 다 외부 공기로 바꿨다.

(외부 공기는 -1이다.) 그다음 면적 2개가 닿는지 판별해서 뭘 죽일지 살릴지 판별했다.

# -*- encoding: cp949 -*-
import Queue
time_count = 0

def bfs(maps):
    visited = [[0 for j in range(m)] for i in range(n)]
    q = Queue.Queue()
    q.put([0,0])
    visited[0][0] = 1
    while not q.empty():
        p = q.get()
        maps[p[0]][p[1]] = -1
        for i in range(4):
            y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            if y>n-1 or x>m-1 or x<0 or y<0:
                continue
            if visited[y][x]==0 and maps[y][x]==0:
                q.put([y,x])
                visited[y][x] = 1

n,m = map(int,raw_input().split())
maps = [map(int,raw_input().split()) for i in range(n)]

while True:
    #print
    #for i in range(n):
    #    for j in range(m):
    #        print '%2d' %maps[i][j],
    #    print

    end = True
    for i in range(n):
        for j in range(m):
            if maps[i][j] > 0:
                end = False
                break
    if end: 
        print time_count
        break
     
    bfs(maps)

    for i in range(n):
        for j in range(m):
            if maps[i][j] > 0:
                sur = 0
                if i-1>=0 and maps[i-1][j] < 0: sur += 1
                if j-1>=0 and maps[i][j-1] < 0: sur += 1
                if i+1<=n-1 and maps[i+1][j] < 0: sur += 1
                if j+1<=m-1 and maps[i][j+1] < 0: sur += 1
                if sur < 2: maps[i][j] = time_count + 1
                else: maps[i][j] = 0

    for i in range(n):
        for j in range(m):
            if maps[i][j] < 0:
                maps[i][j] = 0
    time_count += 1

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030

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

99% 동일한 문제... 정올에서는 카테고리가 백트래킹으로 되있는데 백트래킹으로 하게되면

파이썬이라 리커전 에러가 발생할것 같다.. 백트래킹으로 구현할 경우 외부 공기 판별하는 부분만 

백트래킹식으로 바꿔주면 될것 같다.

# -*- encoding: cp949 -*-
import Queue
time_count = 0
cheese_count = 0

def bfs(maps):
    visited = [[0 for j in range(m)] for i in range(n)]
    q = Queue.Queue()
    q.put([0,0])
    visited[0][0] = 1
    while not q.empty():
        p = q.get()
        maps[p[0]][p[1]] = -1
        for i in range(4):
            y,x = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            if y>n-1 or x>m-1 or x<0 or y<0:
                continue
            if visited[y][x]==0 and maps[y][x]==0:
                q.put([y,x])
                visited[y][x] = 1

n,m = map(int,raw_input().split())
maps = [map(int,raw_input().split()) for i in range(n)]

while True:
    #print
    #for i in range(n):
    #    for j in range(m):
    #        print '%2d' %maps[i][j],
    #    print

    end = True
    for i in range(n):
        for j in range(m):
            if maps[i][j] > 0:
                end = False
                break
    if end: 
        print time_count,'\n',cheese_count
        break
     
    bfs(maps)
    cheese_count = 0
    for i in range(n):
        for j in range(m):
            if maps[i][j] > 0:
                sur = 0; cheese_count += 1
                if i-1>=0 and maps[i-1][j] < 0: sur += 1
                if j-1>=0 and maps[i][j-1] < 0: sur += 1
                if i+1<=n-1 and maps[i+1][j] < 0: sur += 1
                if j+1<=m-1 and maps[i][j+1] < 0: sur += 1
                if sur == 0: maps[i][j] = time_count + 1
                else: maps[i][j] = 0

    for i in range(n):
        for j in range(m):
            if maps[i][j] < 0:
                maps[i][j] = 0
    time_count += 1