[백준 16236] 아기 상어

[ 백준 16236 : 아기 상어 ]

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

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

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

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

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

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

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

[백준 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]) 변수를 설정해 몇번만에 그 번호로 왔는지를 저장했다.

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

[백준 9376] 탈옥

[ 백준 9376 : 탈옥 ]

bfs를 응용한 문제.

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

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

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

[백준 2665] 미로만들기

[ 백준 2665 : 미로만들기 ]

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

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

[백준 16137] 견우와 직녀

[ 백준 16137 : 견우와 직녀 ]

오랜만에 BFS문제를 풀어본것같다. 사실 문제를 읽으면서도 이게 BFS맞겠지 하고 풀었다.
왠만하면 BFS와 DFS같은 문제들은 바로 음 이렇게 풀어야지 하는데 이문제는 한글해석이 너무 어려웠다... 영문을 번역한것도 아닌데 무튼 좀 이상했다ㅋㅋㅋㅋㅋㅋ

첫번째로는 말이 이상하다.

이렇게 되면, 까치와 까마귀에게 굉장히 미안하면서도 민망해지기 때문에 견우는 오작교를 두 번 연속으로 건너는 일은 피하려고 한다.

이런 상황에서도 까마귀와 까치는 견우와 직녀를 도와주고 싶었기 때문에, 견우가 원하는 다리에서 주기가 M 분인 다리를 하나 더 놓아주겠다고 한다. 다만, 아래와 같이 절벽이 가로와 세로로 교차하는 경우에는 까마귀와 까치가 다리를 만들어 줄 수 없다고 한다.

내가 이상한건지는 모르겠는데
두번 연속으로 건너는 일은 피하려고한다. -> 이런 상황에도 까치와 까마귀는 도와준단다
-> 원하는 다리에서 주기M분인 다리를 만들어준다 -> 절벽이 가로세로 교차시엔 안만들어준다.

어떤때는 다리라고하고 어떤때는 오작교라고 하고 처음에 푼게 틀렸다고 나와서 두개가 다른건줄 알았다.

1.그리고 다리에서 M인 다리를 하나 더 놓아준다는게 이미 초기 인풋에 있는 다리에서 이어지는 다리를 만들어준다는 건가????? 이렇게 생각했고
5 5
1 1  0 1   1
2 1  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

2.절벽이 가로와 세로로 교차하는 경우에는 다리를 만들어주지 못한다했으니
5 5
1 1  0 1   1
2 0  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

이런 경우에  는 (1행,2열)의 0에는 다리를 만들수있다는거라 생각했고


또 뭔가 빠진게 견우가 움직이는 시간이다.
견우는 상하좌우 로만 움직일 수 있고 한 칸 이동하는데 1의 시간이 소요된다는 점도 빠져있다. 그래서 1-> 1 이동은 0초인건가????
별의별 생각을 다했는데
방문했는지 안했는지 처리를 잘못해서 계속 틀리는 거였다.

결론으로는 1. 그림은 못만든다. 무조건 만들어준 다리든 원래 있던 다리든 오작교든
다리에서 다리로는 못가게 처리했고
2. 그림은 만들수있게했다. 절벽만 크로스 될때 다리를 못만들게 처리헸다.

맵을 인풋받고 초기에 절벽이 크로스 되는 지점들을 모두 -1로 만들었다.


이제 bfs를 돌렸는데
Queue에 넣을 원소로는 x좌표,y좌표,현재까지의 시간, 만든 다리를 건넜는지 체크

상하좌우를 살펴보면서
1. 현재 1에 있을때 다음이 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
2. 현재 1에 있을때 다음이 0이고 만든 다리를 안건넜다면 배수 시간으로 큐 삽입
3. 현재 0에 있을때 다음은 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
4. 현재 1에 있을때 다음이 2 이상이고 배수 시간으로 큐 삽입
5. 현재 2 이상이고 다음이 1일때 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입

[백준 1765] 닭싸움 팀 정하기

[ 백준 1765 : 닭싸움 팀 정하기 ]


조금 억지스럽게 푼것같은 문제
처음에 문제를 어떻게 풀어야 할지 계속 생각하다가 그냥 완탐으로 풀었다.
문제는 재귀로 풀까 반복문으로 풀까 망설이다가 그냥 큐로 풀었다.

문제가 좀 간단한데 해석하는데 좀 걸렸다. 요즘엔 한국어도 해석이 어렵다...
무튼
F로 나온 사람들은 일단 모두 같은 팀이다.
E인 사람은 그러니까, 원수의 원수는 같은팀이고 이 사람의 친구들도 같은팀이다.
이렇게 생각하면 쉽게 풀리는데

1. 일단 로직은 원수인 사이들을 모두 벡터(E)에 넣고 친구인 사이를 모두 벡터에 집어넣는다(F).
2. 사람 1번부터 N번까지 탐색을 할텐데 만약 현재 살펴봐야할 사람이 이미 팀에 소속되어 있으면 그냥 건너 뛴다.
3. 만약 아무 팀에도 들어가 있지 않는다면 현재 만들어진 팀+1 팀에 들어간다. 그리고 BFS를 돈다.
4. 일단 이 사람 (X) 의 친구들의 친구들 무튼 친구랑 친구관계인 사람들은 모두 내 팀이니 전부 같은 팀으로 넣는다.
5. 원수인 사람은 일단 큐에 집어넣고 첫번째 원수로 표시를 해준다.
6. 첫번째 원수의 원수들(Y)은 모두 현재X의 팀이니 X의 팀으로 표시해 준 후 Y를 큐에 집어넣는다. 물론 Y부터는 친구들을 볼거다. Y의 원수는 건너뛴다.

이런식으로 풀었는데 처음에 한 번 틀렸다. 틀린 이유는 처음에 문제에 나온대로 친구의 친구까지만 같은 팀으로 표시했기 때문이다.
문제를 계속 보다가 결국 이해 했고 친구의 친구의 친구의 친구의....~~ 모두 X의 팀이라고 이해했고 고치니까 맞았다.

코드를 참고하자.

[백준 1697] 숨바꼭질

[ 백준 1697 : 숨바꼭질 ]

문제에 주어진대로 구현하면된다.
수빈이는 x위치일때 x+1 또는 x-1 또는 2*x의 위치로 1초마다 이동할 수 있다.
그럼 BFS탐색을 해준다면 모든 방문을 해주면서 동생이 있는 위치 K에 도달하게 할 수 있다.
그때의 시간이 가장 빠른 시간임이 보장된다.

[백준 1175] 배달

[ 백준 1175 : 배달 ]

간만에 BFS문제~

1분마다 동서남북으로 '#'가 아닌 곳으로 이동하면서 두 곳의 C를 들릴 수 있는 최소의 시간을 구하면된다.

문제에서 체크해야하는 부분은 연속으로 같은 방향으로는 이동 할 수 없다.
이 말은 동->동 이렇게 이동하거나 남->남 이런식으로는 이동 하면 안된다. 무조건 동->(서, 남, 북) 이렇게 다른 방향으로만 이동해야한다.
그리고
목적지가 두 곳이므로 한 곳만 들렸을때 BFS를 종료하면안된다.

목적지 두 곳을 C1,C2라고 해보면 큐에 C1을 들렸는지 C2를 들렸는지도 함께 넣어줘야한다.

그리고 방문을 체크하기 위해 bool VISIT변수를 뒀는데 일단 크기는 교실의 지도범위처럼 [50][50] 선언하고 방향은 총 네곳이므로 [4] 까지 추가한다.
그리고 C1을 들리고 왔는지 C2를 들리고 왔는지 아무곳도 들리지 않았는지도 체크하기 위해 값을 줘야하는데
나는 C1을 들렸을때는 1 C2를 들렸을때는 2 두곳 다 들렸을때는 3 아무곳도 들리지 않았을때는 0 이렇게 줘서 [4]을 추가로 줬다.

그럼 bool VISIT[50][50][4][4] 이렇게 나온다.

이제 BFS를 돌리면된다.
큐에 있는 정보는 X좌표, Y좌표, 이동한 방향, C1들렸는지 C2들렸는지, 시간 이렇게 총 4개이다.

C1과 C2를 1과 2로 체크를 해준다면 0 1 2 3 이렇게 한개의 변수로 모두 처리가 가능하다.

BFS가 끝나도 답이 나오지 않았으면 -1로 출력하고 끝내면된다.

[백준 1967] 트리의 지름

[ 백준 1967 : 트리의 지름 ]

이런 모양의 트리가 있을때 두 개의 점을 양 손으로 잡고 펴본다고 생각하자.
이때 각 간선마다 값이 있는데 이 값의 합이 가장 클 때의 합을 출력하면 된다.

예제의 테스트 케이스는 이렇게 두개의 점을 잡으면 된다고 한다.

처음 문제를 접했을때 LCA라고 생각했다. 총 노드의 갯수가 1000이라고 봤고
1초에 들어오게 풀 수 있다고 생각했다.

그래서 (1,2) (1,3) (1,4) ....(5,6) (5,7) (5,8)....(N-1 , N) 이런식으로
모든 두개의 점을 다 선택하고 그중 최댓값을 찾았는데.. 시간초과가 나왔다.


어떻게 접근할까? 일단 임의의 어떤 한 점에서 DFS를 이용해
가장 긴 거리를 가진 노드A를 찾는다.
그리고 그 노드에서 또 다시 DFS를 이용해 가장 긴 다른 노드B를 찾으면된다.
그러면 A와 B의 거리가 가장 긴 거리임을 알 수 있다.

왜?
임의의 어떤 한 점C를 보면 C에서 가장 먼 거리를 가진 노드 A를 볼 수 있다.
그럼 이 C와 A 사이에 있는 간선들 집합 중에는
무조건 가장 길이가 긴 간선들이 포함되어있을 것이다.
시간은 N-1만큼이 걸릴것이다.

그리고 A점을 기준으로 다시 또 DFS로 전체를 다 본다.
이때 계속 더 탐색하며 현재의 최대값보다 커질때마다 갱신을 해주면 최대값이 나온다.
그리고 이 최대값은 A를 기준으로 가장 긴 노드 B와의 거리가 될 것이다.

[백준 1525] 퍼즐

[ 백준 1525 : 퍼즐 ]

bfs문제..

근데 메모리 제한이 16mb라서 좀 아슬아슬할것 같은데..? 하면서 풀었다.
일단 입력받는 수들을 하나의 문자열로 정의한다.
그러면 s = "103425786" 이라는 문자열이 만들어진다.

이후 큐를 만드는데 상태를 계속 가지고 갈 string과 현재 0 이 있는 인덱스를 알기 위한 int 이렇게 큐에 삽입!
방문했는지 안했는지를 알기위해서 해쉬를 사용했고 이 map에 1이 들어가 있다면 삽입하지 않는다.

맵은 3*3인데 어짜피 맵은 계속해서 이용하지 않을 것이니 그냥 처음부터 일차원으로 받았다.
이차원과 똑같은 방법으로 범위 설정을 해주면 되는데 같은 행에서 움직일때, 같은 열에서 움직일때를 / 와 %를
잘 이용해서 하면된다.


그 후 bfs를 돌린다. 만약 큐의 front와 "123456780"과 일치하다면 프로그램을 바로 끝내면된다.
...

..
아주 아슬아슬하게 통과했다.. 메모리 1만6천kb...

[백준 3184] 양

[ 백준 3184 : 양 ]

입력을 받고 '#' 이 아니고 방문한 좌표가 아니라면 바로 DFS로 들어간다.
들어간 뒤 인접한 상하좌우를 돌면서 o의 갯수와 v의 갯수를 세어준 후
DFS가 끝나면 서로의 갯수를 대소비교를 해준다.
양이 늑대보다 많으면 양을 더해주고 늑대가 양보다 많거나 같으면 늑대를 더해준다.

단순하게 풀 수 있는 문제이다.

[백준 2589] 보물섬

[ 백준 2589 : 보물섬 ]

BFS문제

한 점을 기준으로 얼마나 멀리까지 갈 수 있는지를 묻는 문제이다.
문제에서 계속 함정인지는 모르겠는데 읽기 헷갈리게 최단시간을 계속 언급해서 좀 짜증났다.
뭔가 수능 외국어영역같은 느낌

어떤 한 좌표 값이 L일때 그 좌표에서 최대한 멀리까지 갈 수 있는 값이 답이다.
처음에 컴포넌트마다 따로따로 BFS했는데.. 시간초과가 났다. 쓸데없는짓은 역시 하면 안된다.

먼저 한 좌표를 큐에 넣고 큐가 비어서 사이즈가 0이 될때까지 큐를 돌린다.
큐를 한번 사이클 돌 때마다 값을 +1을해주고
BFS 탐색이 끝날때 값을 비교하면된다.

[백준 9205] 맥주 마시면서 걸어가기

[백준 9205 : 맥주 마시면서 걸어가기 ]

BFS로 쉽게 풀 수 있는 문제였다.
좌표가 -3만..~+3만.. 이라서 맵을 만드는건 불가
로직은 일단 입력을 받고 N개의 좌표와 도착 좌표를 전부 한 배열에 넣었다.
그리고 출발점 좌표와 가지고 있는 맥주 20개를 큐에 넣는다.
그리고 BFS를 돌리는데
큐의 FRONT()를 기준으로 가지고있는 맥주*50>= 거리(FRONT()좌표,입력좌표) 일 경우 다시 큐에 넣는다.
큐에 넣을땐 맥주를 1개부터 20개까지 넣었다.
사실 무조건 20으로 채워서 넣어도 이 문제는 풀리는데
처음에 문제 읽고 출력을 안읽어서 맥주 몇 개를 사야되냐로 알고있었다....

무튼 단순 BFS로 풀면 특별한 함정 없이 쉽게 풀 수 있는 문제.

[백준 14867] 물통

[백준 14867 : 물통 ]

BFS를 사용하면 쉽게 풀 수 있는 문제

처음 문제를 접했을때 A와 B의 물통의 MAX값이 10만이라서 이차원 배열도 생성안되고 어떻게 해야하나 고민했었다.
그러다가 처음 시도해본건 그냥 VISIT배열 없이 계속 돌리다가 찾으면 종료시키고 count변수를 하나 둬서 count가 몇 천이 넘어가면 그냥 -1 출력했는데
역시 이런 야매방법은 통하지 않는다. 메모리초과와 시간초과 틀렸습니다가 골고루 나왔었다.
다음으로 생각했던 방법은
해쉬값을 이용하는 것이었다. 현재 A의 물 양에 100만을 곱한다 + 현재 B의 물 양 을 더한다.
그리고 이 수를 해싱해서 충돌은 VECTOR에 넣었는데 시간초과+메모리초과 가났다.

어떻게해야될까?

사실 간단하다.
이 물통의 경우의 수는 네가지이다.
A = 어떤 값 | B = 0
A = 어떤 값 | B = B_MAX
A = 0 | B = 어떤 값
A = A_MAX | B = 어떤 값

이런 네가지 경우를 체크함수로 만들면된다.
어떤 값은 0~100000 일테고 경우는 네 가지 이므로
VISIT[100001][4] = {0,}으로 선언하면된다.

BFS 알고리즘으로 풀 것이므로 무조건 더 먼저 (A의 종료조건 && B의 종료조건) 에 충족하는 것이 답이된다.
끝까지 안나오면 WHILE문을 빠져 나올것이고 -1을 출력한다.

[백준 7569] 토마토

[백준 7569 : 토마토 ]

전형적인 BFS문제.

처음 알고리즘 문제를 접한게 A+B, A-B 말고 BFS와 DFS였다.
이 알고리즘을 모르면 아무것도 못한다는 말에 엄청나게 풀었던 기억이 난다.

이 문제 처음보고 아 전에도 이런거 풀어봤는데 뭐더라 했는데
혹시 비슷한 문제 풀고싶은 누군가를 위해..
[백준 6593 : 상범빌딩 ]
똑같이 풀면된다.

이 문제 나는 3번을 틀렸다..
어휴...
틀린이유 1
입력받는 배열은 층-행-열 순으로 저장하고 큐는 행-열-층 순으로 저장하다보니
BFS과정에서 잘못 넣고 있었다... 깨닫고 병ㅅ 소리만 한 다섯번 했다.

근데 또 틀렸다..

틀린이유 2
큐를 구현했는데 100*100*3..? 왜 큐사이즈를 이렇게 잡았는지 아직도 이해가 안간다.
무슨 이유였는지 생각도 안나는데 짜증나서
555만으로 최대 큐 사이즈 잡으니 당연히 통과


실수를 줄이자!

[백준 2573] 빙산

[백준 2573 : 빙산 ]

dfs+bfs문제이다.
숫자들이 빙산이고 dfs로 컴포넌트 갯수를 찾는다.
한번 싸이클이 돌 때
한 숫자마다 위, 아래, 오른쪽, 왼쪽 방향이 비어있는만큼 빼주면된다.

오랜만에 bfs와 dfs문제 풀때마다 초심으로 돌아가는 느낌이라서 좋다ㅎ

[백준 1532] 동전교환

[백준온라인저지 1532 : 동전교환 ]

풀긴 풀었는데 맞게 푼건가... 싶은 문제 혹시 누군가 이 글을 보게 된다면 더 쉬운 풀이
혹은 더 좋은 방법을 알려줬으면 좋겠다.ㅜㅠ


일단 문제는 G1,S1,B1 개의 금화, 은화, 동화를  가지고 있는데 G2,S2,B2개로 교환하려고한다.
이때 최소 몇번 만에 교환을 할 수 있는가?

교환 종류는
금 1개는 은 9개
은 11개는 금 1개
은 1개는 동9개
동 11개는 은 1개
이렇게 4종류만 된다.

BFS로 풀어야 된다고는 생각했는데 메모리가 터져버리거나 시간이 초과되서
단순 BFS는 안되었다..
그래서 초반에 계산으로 가능한 부분들을 최대한 처리해버리기로 했다.
필요한 은화 갯수를 먼저 금으로 최대한 충당시켰다.
그리고 필요한 동화 갯수를 은으로 최대한 충당시켰다.
이 후에 남은 금 갯수를 은으로 최대한 바꾸면서
이 과정에서 S1이 S2보다 작을때까지 계속 동화로 바꾸었다.

이러한 일련의 과정들에서 G1,S1,B1이 G2,S2,B2와 같으면 바로 답을 출력하도록했다.

그후에 현재 G1,S1,B1을 큐에넣고 BFS를 돌렸는데
이미 전처리 과정을 심하게 거쳐서인지 BFS 몇번 돌지도 않고 끝나버렸다.ㅋㅋ.

이문제 정말 10번 넘게 틀렸는데 스트레스 받았었다..