[파이썬]NHN공채 Pre-Test 1차 기출문제 풀이

[파이썬]NHN공채 Pre-Test 1차 기출문제 풀이

300x250

NHN그룹 공개 채용 광고를 보고 pre-test 난이도를 파악하기 위해 들어가서 기출문제를 확인해보니 사용언어가 C, C++, JAVA로 제한되어있었습니다.

그렇기에 시험과 무관하게 이 기출 문제를 파이썬으로 다룬 곳 또한 없을 듯하여 글을 작성해보았습니다.

문제는 다음과 같습니다.

예시 입출력

깊이 우선 탐색(DFS)를 활용한 문제 풀이

1, 주어진 행렬의 1을 방문할 수 있는 곳, 0을 방문할 수 없는 곳이라고 정의한 후 주어진 행렬을 하나씩 확인합니다.

2, 1을 방문했다면 재귀함수를 호출하여 주변을 확인하면서 1이면 0으로 바꾸고 방문한 수만큼 count를 합니다.

3, 행렬을 벗어나지 않으면서 확인 중인 좌표 주변에 방문할 수 있는 곳이 없는 상태에 최종적인 count값을 리스트에 저장합니다.

4, 다시 반복하는 과정에서 1을 방문한다면 2,3번의 과정을 다시 반복합니다.

여기까지만 했을 때, 위의 입력 1의 예시를 입력할 경우 이중 반복문을 순차적으로 반복하기 때문에 리스트에는 4 7 5가 저장되는데 이 문제의 출력 예시는 전부 오름차순으로 정렬되어있기 때문에 오름차순 정렬을 하고 리스트의 개수와 리스트를 문자열로 전환하여 문제를 해결할 수 있습니다.

풀이

def dfs(x,y): if x<=-1 or x>=n or y<=-1 or y>=n: pass else: if Mat[x][y] == 1: Mat[x][y] = 0 List[Count]+=1 dfs(x - 1, y) dfs(x, y - 1) dfs(x + 1, y) dfs(x, y + 1) n=int(input()) Mat=[(list(map(int,input().split()))) for _ in range(n)] List=[] Count=0 for i in range(n): for j in range(n): if Mat[i][j]==1: List.append(0) dfs(i,j) Count+=1 List.sort() print(len(List)) print(' '.join(map(str,List)))

2021 NHN그룹 공채 기출 문제 PDF파일

프리테스트_1차_기출문제.pdf 0.21MB

NHN그룹 채용 공고 사이트: https://recruit.nhn.com/ent/index

from http://lbdiaryl.tistory.com/171 by ccl(A) rewrite - 2021-10-05 17:01:51