마코

https://school.programmers.co.kr/learn/courses/30/lessons/72412

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

접근

• 2중 for문으로 query마다 info를 전부 순회하면 정확성은 통과하지만 O(n^2)으로 효율성 테스트에서 실패한다.
• info를 Map<개발언어 + 직군 + 경력 + 소울푸드, List<점수>>로 저장, 점수를 내림차순 정렬한다.
• 각 query를 key로 infoMap에서 List<점수> 를 조회, 내림차순 되어있기 때문에 query의 점수보다 낮은 첫 번째 인덱스가 합격한 사람의 숫자이다.
  • 각 query에서 -인 경우 모든 경우를 조회해야 하기 때문에 모든 대상을 탐색 대상에 추가한다. ex) if 개발언어 = '-' 인 경우 cpp, java, python을 모두 탐색 대상으로 지정한다.
  • query 점수보다 낮은 첫 번째 인덱스를 순차 탐색하면 효율성 테스트에서 시간 초과가 발생한다. 이를 해결하기 위해 이분 탐색을 이용했다.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/72412.%E2%80%85%EC%88%9C%EC%9C%84%E2%80%85%EA%B2%80%EC%83%89/%EC%88%9C%EC%9C%84%E2%80%85%EA%B2%80%EC%83%89.java

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

접근

• 우선순위 큐에 모든 파일의 크기를 넣는다.
• 큐에서 두 요소를 꺼내고 두 개를 더한 값을 큐에 다시 넣고, sum에도 더한다.
• 결과인 sum을 출력

요소는 K는 최대 10^6이고 파일의 최대 크기는 10,000 이므로 int로 계산하면 오버플로우가 발생하니 long으로 계산하자.

코드

https://github.com/aak2075/algorithm-baekjoon/blob/main/%EB%B0%B1%EC%A4%80/Gold/13975.%E2%80%85%ED%8C%8C%EC%9D%BC%E2%80%85%ED%95%A9%EC%B9%98%EA%B8%B0%E2%80%853/%ED%8C%8C%EC%9D%BC%E2%80%85%ED%95%A9%EC%B9%98%EA%B8%B0%E2%80%853.java

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

접근

• 입력에 따른 좌표 평면coordinate를 만든다.
• coordinate를 순회하며 값이 2인(바이러스를 담을 수 있는) 좌표를 담은 canVirus를 만든다.
• 백트래킹으로 coordinate를 순회하며 바이러스를 m개 놓을 수 있는 모든 경우의 수를 담은 cases를 만든다.
  • coordinate를 순회하며 값이 2인 좌표를 cases에 add
  • 백트래킹의 decision spaces는 해당 좌표를 선택하는 경우와 선택하지 않는 경우로 구성한다.
• cases마다 bfs 탐색으로 탐색의 성공하는 depth를 계산하여 이 중 가장 작은 depth를 계산하면 끝
  • cases 중에서 선택된 case라면 bfs큐에 삽입
  • 선택되지 않은 case라면 빈 칸으로 변경하기 위해 copyCoordinate의 해당 좌표를 0으로 변경한다

코드

https://github.com/aak2075/algorithm-baekjoon/tree/main/%EB%B0%B1%EC%A4%80/Gold/17141.%E2%80%85%EC%97%B0%EA%B5%AC%EC%86%8C%E2%80%852

[https://school.programmers.co.kr/learn/courses/30/lessons/42862#]

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

접근

• 0부터 n+1까지 clothes 리스트를 1로 초기화 한다.
  • lost나 reserve는 첫 번째 학생을 0번이 아닌 1번으로 입력하기 때문에 주의
• 정렬되었다는 언급이 없기 때문에 reserve를 오름차순 정렬한다.
• reserve[i] 번째 clothes의 원소를 2로 변경한다.
• lost[i] 번째 clothes의 원소에서 1을 뺀다.
  • 여분이 있는 학생도 체육복을 도난당할 수 있고 이 경우 2개 -> 1개가 되므로 0으로 초기화 하는 실수를 하면 안된다.
• reserve를 순회하면서 여분이 있는 학생은 앞이 체육복이 없으면 앞에 빌려주고 뒤가 체육복이 없으면 뒤에 빌려준다
  • 순회시 reserve[i] 번째가 도난당해서 1이면 빌려줄 수 없기 때문에 2인지 검사한다.
  • 인덱스 초과 주의

해결 방법론 - 현재 상황에서 최적의 해를 구하는 그리디 알고리즘을 사용하여 해결.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv1/42862.%E2%80%85%EC%B2%B4%EC%9C%A1%EB%B3%B5/%EC%B2%B4%EC%9C%A1%EB%B3%B5.java

[https://school.programmers.co.kr/learn/courses/30/lessons/87694]

문제

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
itemX, itemY는 1 이상 50 이하인 자연수입니다.
지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

접근

• 모든 좌표를 x 2 한다
  • 경로가 이어져 있지 않더라도 거리가 1이면 갈 수 있게 되기 때문에 이를 방지하기 위해 x2를 함.
• 0부터 100까지의 좌표 전부를 false 처리한다.
• 각 rectangle x 2 좌표를 전부 true 처리한다.
• 각 rectangle의 안쪽을 false 처리한다
  • 왼쪽 끝의  x +1 부터 오른쪽 끝의 x -1 까지
  • 아래 끝의 y + 1부터 위 끝의 y - 1까지
• 좌표에서 true인 부분을 따라서 bfs 탐색을 수행한다
  • 방문 처리를 통해 재방문을 방지한다
  • 좌표의 범위를 벗어난 위치는 방문하지 않는다
  • 좌표마다 depth를 기록, 다음 위치에서는 이전 좌표의 depth + 1로 계산한다
• 처음에 좌표에 x2를 해주었기 때문에 결과로 나온 depth를 다시 2로 나누어주면 끝.

코드

• https://github.com/aak2075/algorithm-baekjoon/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/87694.%E2%80%85%EC%95%84%EC%9D%B4%ED%85%9C%E2%80%85%EC%A4%8D%EA%B8%B0/%EC%95%84%EC%9D%B4%ED%85%9C%E2%80%85%EC%A4%8D%EA%B8%B0.java

https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.

접근

• 각 단어를 정점으로 한다.
• 인접 리스트로 알파벳 차이가 하나인 것끼리 인접 리스트에 추가한다.
  • 각 문자별로 하나씩 비교해서 다른 것의 개수가 1개 이어야 한다.
• begin부터 bfs탐색으로 target을 찾게되는 최솟값을 찾는다.
  
  • 이미 탐색한 정점은 방문 처리하고 재방문하지 않는다.
  • 정점에 대한 깊이를 저장하고 다음 정점의 깊이는 현재 정점의 깊이 + 1

예외 사항 - words안에 target이 없다면 아예 갈 수 없기 때문에 0을 반환하고 종료해야 하는데 이 처리를 안해주면 words에 없더라도 target 정점을 도달이 가능하여 예상치 못한 값이 나올 수 있다.

문자열이고 중복이 불가능하기 때문에 인접 리스트를 Map<String, List<String>>으로 구현했다. 이 문제에서는 괜찮지만 중복이 존재하는 경우 Map을 사용하면 결과가 달라질 수 있기 때문에 주의하자. (왠만해서는 List로 구현하는 것이 나아 보이고 이 문제도 인덱스로 처리하면 가능하다.)

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/43163.%E2%80%85%EB%8B%A8%EC%96%B4%E2%80%85%EB%B3%80%ED%99%98

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항
maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

접근

• 최단 경로로 목적지까지 갈 수 있는지와 그 거리를 계산하는 문제.
• 좌표로 계산하여 상, 하, 좌, 우를 갈 수 있는지 판단하고 갈 수 있다면 큐에 좌표를 담아 bfs탐색을 수행한다.
  • 이동할 x, y좌표가 0 미만이거나 m, n이상인 경우는 갈 수 없다
  • 이동할 x, y좌표가 이미 방문했다면 갈 수 없다.
  • 이동할 x,y 좌표에 벽이 있다면(0이면) 갈 수 없다.
  • 갈 수 있다면 큐에 이동할 좌표를 offer한다.
  • 갈 수 있다면 이동할 좌표를 방문 처리 한다.
  • 갈 수 있다면 현재 좌표의 깊이 + 1을 이동할 좌표의 깊이로 설정한다.
• 큐에서 좌표를 꺼낸 좌표가 도착 지점일 경우 해당 좌표의 깊이를 반환.

깊이를 int로 계산해보려다가 헤멨던 문제.

깊이도 depth[nextY][nextX] = depth[y][x] + 1 이렇게 좌표로 표현하여 해결했다.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/1844.%E2%80%85%EA%B2%8C%EC%9E%84%E2%80%85%EB%A7%B5%E2%80%85%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC

https://school.programmers.co.kr/learn/courses/30/lessons/43162

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/43162)

문제

문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.

접근

• 각 연결된 정점들의 부분집합을 컴포넌트라고 부른다.
• 각 정점에서 bfs를 수행하고 그 횟수를 세면 된다.
• 방문한 점은 visited 처리하기 때문에 각 정점마다 bfs를 수행할 때 방문하지 않은, 즉 연결되어있지 않은 정점의 경우에 bfs를 수행한다.

코드

• https://github.com/aak2075/algorithm-baekjoon/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv3/43162.%E2%80%85%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC