[백준 16236] 아기 상어

[ 백준 16236 : 아기 상어 ]

2018 삼성전자 sw직무 하반기 기출문제입니다.

역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다.

저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 답이나오는 문제로
입력값의 범위도 작아서 별로 생각할 것이 없습니다. 길면 40분? 짧으면 15분이나 20분에 끝낼만한 문제라고 생각합니다.

일단 구조체로 상어의 정보를 입력합니다. 좌표,먹은 물고기갯수,상어 크기.
그리고 BFS를 이용해 현재 상어의 좌표에서 물고기들마다의 좌표와 거리를 계산합니다.
거리가 같다면 X의 좌표가 더 작은것
거리가 같고 X의 좌표가 같다면 Y의 좌표가 더 작은것

이렇게 결과 좌표와 거리를 갱신해 나가면서 큐에 아무것도 남지않아 BFS탐색을 완료한 후

상어구조체의 값들을 갱신합니다. 갱신된 좌표, 물고기갯수++,상어크기(조건)
그리고 갱신된 거리를 답에 더해줍니다.

상어가 더이상 이동하지 못한다면 더해진 답을 출력한 후 프로그램을 종료하면 됩니다.

[백준 16235] 나무 재테크

[ 백준 16235 : 나무 재테크 ]

2018 삼성전자 sw직무 하반기 기출문제 입니다.
문제는 단순 구현에 소팅을 어떤식으로 진행하는지가 관건이 되는 문제 같습니다.
역시나 이문제도 역대 삼성전자 기출문제처럼 조건을 빼먹지 않고 구현을 하면 되는 문제입니다.

저는 (봄,여름) (가을) (겨울) 이런식으로 함수를 짜서 k만큼 반복을 해서 마지막에 살아있는 나무들의 갯수를 셌는데
이차원 벡터에 나무를 직접 심어주고 죽여주고 이런식으로 진행했습니다.


봄에는 무조건 양분이 나무의 나이만큼 있으면 나무의 나이를 ++ 해주고 양분의 양을 나무 나이만큼 - 해줍니다.
그리고 나무의 나이가 5로 나누어떨어지는지를 여기서 체크를 미리해 5로 나누어 떨어진다면 큐에 집어넣어줍니다.
또한, 나무의 나이만큼 양분이 없다면 그 이후로는 벡터에 있는 값들을 pop_back해가면서 나이/2 만큼 양분에 더해줍니다.

이렇게 봄,여름 과정을 끝내고 가을 함수를 준비합니다.
가을에는 큐에 집어넣은 나무들을 BFS알고리즘을 이용해 주위 8방향으로 번식시킵니다.
겨울에는 처음 입력한 양분만큼 더해주는데 이걸 봄 여름과정에서 해도 될듯합니당.


그냥 k만큼 반복한 후의 이차원 벡터의 크기가 답이 됩니다.

[백준 16234] 인구 이동

[ 백준 16234 : 인구 이동 ]

요번 삼성전자 2018 하반기 sw기출문제 입니다. 오전 시간에 나왔던 문제라고 하네요.

지금까지 삼성전자 기출문제들을 살펴보면 대체로 bfs, dfs, 완전탐색, dp로 나뉘는데 이것도 역시 그 범주안에 들어가는것 같네요.

3시간에 두문제니까 한문제당 1시간 30분씩만 풀어도 충분한... 아마 대부분 30분안에들 푸셨을 것으로 예상됩니다.
따로 복잡한건 없고 문제에 나온 그대로 구현만 시켜주면되기 때문에 시간이 오래 걸릴것같진 않습니다.

제가 푼 로직은

1. 입력
2. CHK변수를 통해 인구가 이동하지 않으면 프로그램을 끝냅니다.
3. DFS를 통해 한 컴포넌트의 국가 갯수와 인구의 합을 리턴합니다.
4. 큐에 좌표와 컴포넌트 인덱스를 집어넣어 국가들의 인구수를 맞춰줍니다.

큐와 재귀를 이용해 풀었는데 뭐 어떻게 구현하던 시간이나 메모리에서 에러가 뜰 법한 문제는 아니라서 다들 쉽게 구현했을것같습니다.

[백준 5213] 과외맨

[ 백준 5213 : 과외맨 ]

BFS + DFS 를 이용하는 문제

일단 맵이 정말 특이하게 생겼다. 보통 보던 N*M의 직사각형의 모양이 아니라 짝수번째 행은 맨 처음과 마지막 열이 비어있다.

문제를 풀 때 고려할 것은 이것 뿐인것같다.

처음 0,0에서 출발해서 상하좌우를 체크하며 돌아다니는 것은 BFS를 이용했고,
문제의 답을 출력해야하는 경로와 지나온 칸의 수는 DFS를 이용했다.

일단 문제에서 그려진대로 똑같이 맵을 만들었다. 삼차원배열로 맵을 입력받았는데
MAT이라는 변수의 [0][X좌표][Y좌표] 는 입력하는 값들, 그리고 [1][X][Y]에는 해당 맵의 숫자를 입력했다.
내가 만든 맵은 0행0열부터 시작하므로 짝수행은 0~2*N-1까지 열이 존재하고 홀수행은 1~2*N-2까지 열이 존재한다.
홀수행과 짝수행은 ( 행&1 )으로 쉽게 구할 수 있다.

그리고 마지막 경로를 DFS로 탐색하기 위해 해당 번호마다 지나온 번호를 입력했고,
한번 탐색했던곳을 쓸모없이 다시 탐색하지 않기 위해서 지나온 좌표마다 그때까지 이동한 순서를 넣어줬다.
이 처리를 함으로써 한 번 지나왔지만 만약 그곳을 3번만에 왔고, 지금은 2번만에 그곳을 가는 것이라면 해당 좌표를 큐에 넣는 식으로 구현했다.
또 하나의 처리를 더해줬는데,
맵의 한 번호마다 두개의 좌표가 달려있어 이를 묶어서 처리하기 위해 (VI[500*500]) 변수를 설정해 몇번만에 그 번호로 왔는지를 저장했다.

따라서
이차원 배열로 해당 좌표까지 얼마만에 왔는지, 일차원 배열로 해당 번호까지 얼마만에 왔는지, 일차원 배열로 지나온 좌표를 저장.
이런식으로 구현했다.

[백준 11501] 주식

[ 백준 11501 : 주식 ]

그리디 문제였다.
생각만 하면 쉬운 문제라고 생각한다. 처음에 dp인가? 라고 생각하면서 테스트 케이스를 하나씩 풀어보다가 그냥 단순하게 풀 수 있겠다 싶어서
제출 했는데 맞았습니다! 가 떠서 으음! 다행이다

idx라는 변수에 배열의 가장 마지막 값을 입력한다.
그리고 배열을 뒤에서부터 탐색하면서 만약 현재 탐색하고 있는 값이 idx보다 크다면 idx에 배열의 값을 넣는다.
만약 idx보다 작다면 idx에서 탐색하는 값을 뺀 값을 답으로 출력할 변수에 더한다.

[백준 9376] 탈옥

[ 백준 9376 : 탈옥 ]

bfs를 응용한 문제.

꽤 생각하고 풀었던 문제이다. 일단 죄수 두 명 중 한 명이 문을 이미 열었다면 그 문은 다른 죄수가 열지 않아도 되는데
이 처리를 어떻게 해야하나 고민했다.

문제를 해결한 방법은
주어진 입력의 바깥 부분을 모두 '.'으로 채웠다. 0,0에서 bfs를 출발하여 임의의 방문 배열을 주고 해당 좌표마다 문을 얼마나 깨고 갔는지를 체크했다.
그리고 두 죄수의 좌표에서 bfs를 실행했고 위와 똑같이 방문배열에 문을 깨고 간 만큼을 입력했다.

그럼 총 이차원 방문 배열이 3개가 나온다. 이 3개를 모두 더한 후 최솟값을 찾았다.
하지만 문이 위치한 곳이라면 -2를 해줬다. 두 죄수 + 외부에서 출발한 임의의 사람 이 동시에 다 같이 문을 연것이기 때문에 -2를 해줬다.

[백준 2665] 미로만들기

[ 백준 2665 : 미로만들기 ]

간단한 bfs문제
벽을 최소한으로 부수고 목적지까지 가면된다.

기본 bfs처럼 상하좌우를 탐색한 후 만약 검은방인 0 이라면 큐에 현재 벽을 부순 개수+1 을 push 하고 흰방인 1 이라면 그대로 push를 하면 된다.
방문했는지 안했는지를 체크하기 위해 int형 이차원 배열을 이용해 그 자리까지 벽을 부수고 온 갯수를 집어 넣었다.
만약
다음 가야할 좌표의 방문 이차원 배열의 수가 현재 벽을 부순 개수보다 크다면 이동을 하고 작다면 해당 좌표로 이동하지 않으면 된다.