[백준]2468 안전영역 [Python]

 

 

위의 문제는 입력한 N의 개수만큼 N*N의 데이터를 입력하면 h 높이 (1~100)에 따라 물에 잠기지 않는 안전한 영역의 최댓값을 구하는 문제입니다.

 

우선 n을 입력하고 최대값을 넣어줄 ans라는 값과 2차원 배열로 데이터를 입력하는 방법입니다.

h 높이에 따라서 최대값을 구해야하므로 범위를 1이상 101미만으로 for문을 돌려줍니다.

for문을 돌려줄때 최대값을 return 받아서 ans로 넘겨줘서 반복할 때마다 가장 높은 max값을 뽑아주는 방식으로 구현합니다.

 

아래 코드는 위의 코드에서 호출한 solve(h) 함수입니다.

안전 영역 값을 카운트해줄 cnt 를 0으로 초기화해줍니다. 그리고 이중 for 문으로 전체 입력받은 행렬을 값으로 불러올 수 있도록 해줍니다.

 

v[i][j] 값이 0 이라는 말은 아직 방문하지 않은 노드라는 말입니다. v[i][j]값이 0이고 graph행렬의 [i][j]값이 높이인 h보다 클때 조건을 만족합니다.

 

높이보다 값의 크기가 높아야 물에 잠기지 않기 때문에 잠기지 않는 부분을 체크하는 로직입니다.

 

다음에 bfs(i,j,h)함수 호출을 통해 다음 bfs함수를 호출합니다. 아직 bfs함수가 끝나지않았으므로 bfs함수가 끝나고나면 cnt를 +1시켜서 안전영역개수를 늘려줍니다.

 

위에서 bfs함수를 호출하면 아래의 함수가 호출됩니다.

 

bfs의 특징상 queue를 만들어주고 그 queue를 활용하여 데이터를 넣고 빼고 반복을 해서 코드가 진행됩니다.

 

우선 전달받은 i,j 값에 해당하는 v[i][j]를 1(방문) 처리해주고 while문을 돌려서 queue에 데이터가 다 빠질때까지 안에 코드를 반복합니다.

 

그렇게 되면 인접한 노드들을 찾을 수 없을 때 까지 조회하게됩니다.

 

queue에 있는 값을 popleft로 값을 빼낸다음에 그 값을 통해서 인접 노드를 찾습니다.

 

상 하 좌 우에 있는지를 확인해야하므로 (-1,0) , (1,0), (0,-1), (0,1) 을 값에 넣어서 확인해줍니다.

 

전체 범위에서 벗어나면 안되니까 상하좌우를 더한 값인 ni,nj값이 0<=ni<n and 0<=nj<n일 때만 if 문을 수행합니다.

찾은 인접한 노드들을 다시 queue에 append하고 v[ni][nj] =1(방문) 처리하고 남은 queue에 데이터가 없어질때까지 반복하면서 

하나의 높이 (예를 들어 지금은 처음 수행이니까 h=1입니다.)를 돌렸을 때 안전한 영역의 카운트를 찾습니다. 

높이 별 카운트를 다 찾았으면 반복문이 끝나게됩니다.

 

 

전체 코드