. 날씨의 아이 (백준 2468번 : 안전 영역)
본문 바로가기
프로그래밍 공부/백뚠

날씨의 아이 (백준 2468번 : 안전 영역)

by 불냥이_ 2020. 12. 15.

2468번: 안전 영역 (acmicpc.net)

 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

- 대전략

(0,0)부터 탐색을 시작한다. 만약 (0,0)이 T(그림 상 흰색)라면 카운트 (안전영역) 갯수를 올리고, dx dy로 상하좌우에 방문해본다. 만약 경계선이거나 F라면은 그냥 놔두고, T인 곳을 방문한다. (재귀함수 실행)

 그런데 여기는 카운트를 올리면 안되지 않는가? (이어진 곳이기 때문에) 이를 어떻게 처리할 것인가. 시작은 이중 for문으로 돌리고 탐색만 bfs로 처리할 것인가? 

 

 일단 시작해보자. 시작은 다음과 같다.

import sys


N = int(sys.stdin.readline())
plate = [[0 for col in range(N)] for row in range(N)]

for i in range(N):
    for j in range(N):
        if plate[j][i]:
            bfs(i,j)

 그다음 함수를 짜보자. 함수의 순서는 다음과 같다.

1. 해당 위치를 F로 바꾼다. 

2. 상하좌우의 TF를 판별한다. 

3. 만약 T라면 bfs를 실행한다. 

def bfs(x,y):
    plate[x][y]
    for z in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (nx < 0 or nx >= n or ny < 0 or ny >= 6) : continue

        if plate[nx][ny] == F : continue

        if plate[nx][ny] == T :
            bfs(nx,ny)

그리고 N 이 주어졌을 때, 그 숫자 이하는 F를 시키는 코드도 구현하자. 

def initializing(N):
    for i in range(N):
        for j in range(N):
            if plate[i][j] <= N:
                plate[i][j] = False
            else:
                plate[i][j] = True

 

구현하다가 한가지 놓친 게 있다.

문제가 요구하는 것은 일정한 높이가 주어졌을 때, 안전영역을 구하는 것이 아닌

높이는 0~ 이고, 안전영역의 '수'가 최대로 나올 때의 그 수를 구하는 것이다. 

 

일단 높이가 주어졌을 때 (지금은 N으로 설정했다.) 안전영역의 개수를 도출하는 것부터 구현해보자. 

mport sys

N = int(sys.stdin.readline())

plate = [[0 for col in range(N)] for row in range(N)]
count = 0




dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]

def bfs(x,y):
    plate[x][y] = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (nx < 0 or nx >= N or ny < 0 or ny >= N) : continue

        if plate[nx][ny] == False : continue

        if plate[nx][ny] == True :
            print(nx,",",ny,"에서 실행")
            bfs(nx,ny)


def result(u):
    print("--------------------------------------")
    if u == 0: # 정답
        for i in range(0,N):
            for j in range(0,N):
                if plate[i][j]:
                    print("■", end=' ')
                else:
                    print("□", end=' ')
                
            print()
    print("--------------------------------------")
    return


def initializing(N):
    for i in range(N):
        for j in range(N):
            if plate[i][j] <= N:
                plate[i][j] = False
            else:
                plate[i][j] = True
    print("초기화")
    result(0)



for i in range(N):
        plate[i] = [int(x) for x in input().strip().split()]

initializing(N)

for i in range(N):
    for j in range(N):
        if plate[i][j]:
            print("x:",i,"y:",j)
            count += 1
            bfs(i,j)



result(0)
print(count)

구동을 하면

구동 결과

 

와 같이 제대로 전 영역을 F로 만들면서 안전영역을 카운트(5) 했다. 

 

이제 높이를 0부터 올려가면서 최대 안전영역 수를 셀 수 있도록 구현해보자. 

높이는 for문으로 1에서 100까지로 지정하고 max_count를 만들어 count가 최대가 되면 바꿔치기 해주겠다. 

높이가 바뀔때마다 plate를 전부 T로 바꿔준 다음, 높이 이하의 영역은 False해주는 것도 넣어야한다. 

 

심사 성공한 코드는 하기와 같다.

import sys

sys.stdin = open("textfile1.txt","rt")
sys.setrecursionlimit(100000000)
# a = int(sys.stdin.readline())
# a,b = map(int,input().split())
# a = [int(x) for x in input().strip().split()]

N = int(sys.stdin.readline())

ini_plate = [[0 for col in range(N)] for row in range(N)]
plate = [[0 for col in range(N)] for row in range(N)]

max_count = 0



dx=[-1, 1, 0, 0]
dy=[0, 0, -1, 1]

def bfs(x,y):
    plate[x][y] = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (nx < 0 or nx >= N or ny < 0 or ny >= N) : continue

        if plate[nx][ny] == False : continue

        if plate[nx][ny] == True :
            #print(nx,",",ny,"에서 실행")
            bfs(nx,ny)


def result(u):
    print("--------------------------------------")
    if u == 0: # 정답
        for i in range(0,N):
            for j in range(0,N):
                if plate[i][j]:
                    print("■", end=' ')
                else:
                    print("□", end=' ')
                
            print()
    print("--------------------------------------")
    return


def initializing(N, height): # N = 행열의 수, height = 높이
    for i in range(N):
        plate[i] = ini_plate[i][::]
        #print(ini_plate[i])
        #print(plate[i])
        for j in range(N):
            if plate[i][j] <= height:
                plate[i][j] = False
            else:
                plate[i][j] = True
    #result(0)



for i in range(N):
        ini_plate[i] = [int(x) for x in input().strip().split()] # 높이 정보가 ini_plate에 저장됨


# 실행 
for k in range(0,100):
    count = 0
    #print("높이 ", k, "에서 초기화")
    initializing(N, k)
    for i in range(N):
        for j in range(N):
            if plate[i][j]:
                #print("x:",i,"y:",j)
                count += 1
                bfs(i,j)
    if count > max_count:
        max_count = count
    print("count:",count)



#result(0)
print(max_count)

 

댓글