난이도 : GOLD I > 문제링크 : https://www.acmicpc.net/problem/4991 문제해결 아이디어 처음 내가 생각한 방법은 다음과 같다. 순열을 통해서 먼지순서를 정하고 각각의 먼지순서간의 최단거리의 합을 구하고 (bfs 사용) 그중에 가장 낮은 값 이렇게 구하니 시간초과가 났다. 사실 먼지 개수가 10까지 되서 10! * 10 * bfs 니까 당연한 결과이기도 하다. 소스코드(오답) 어느부분을 손대서 시간복잡도를 줄여야 할지 감을 못잡겠어서 다른사람 풀이를 참고했다. 다른 사람의 순서는 청소기로부터의 먼지 거리를 구하고 (1차원 배열) 2차원 배열로 각각의 먼지간의 거리를 구한다. 순열을 통해서 청소하는 먼지의 순서를 섞는다. 2차원 배열을 통해 각각의 먼지거리의 합을 구한다. 최솟값 비교. 각 먼지를 돌면서 bfs를 통해 다른 먼지들간의 최단거리를 이차원배열에 저장함으로써 시간

난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/14502 문제해결 아이디어 먼저 벽을 꼭 3개를 세워야하므로 벽을 3개 세웠을 때 바이러스를 퍼트려야한다. 바이러스는 상하좌우의 인접한 빈칸으로 이동하므로 bfs를 여기서 사용한다. 바이러스의 위치를 큐에 전부 넣고 while q를 돌린다. 바이러스를 퍼트린 후에 0(빈칸) 이 몇개있는지 체크하고, 최대값을 찾는다. 소스코드

난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/6087 문제해결 아이디어 마냥 최단거리 문제가 아닌 거울을 횟수를 최소화 하는 문제이므로 최단거리보다 더 많은 방문을 거치며 도착했음에도 거울개수가 더적은 경우가 있다. 이에 방문했던곳을 재방문할때 거울 사용횟수가 더 적은 경우에만 재방문 가능하게 했다. 소스코드

난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/17471 문제해결 아이디어 조합을 통해서 선거구를 나눈다. ex) (1,2,3),(4,5,6) bfs를 통해 해당 선거구가 연결 되어있는지 확인. 각각의 선거구가 연걸되어있다면 최솟값 비교 소스코드 from itertools import combinations from collections import deque import sys input = sys.stdin.readline n = int(input()) population = [0] + list(map(int, input().split())) graph = [[] for _ in range(n + 1)] for i in range(1, n + 1): arr = list(map(int, input().split()))[1:] graph[i].extend(arr) INF

난이도 : GOLD II > 문제링크 : https://www.acmicpc.net/problem/2933 문제해결 아이디어 화살을 쏜다 left, right 번갈아가면서 없어진 미네랄의 상,하,좌,우에 미네랄이 있으면 dq에 넣는다.(클러스터) q(클러스터)를 탐색하면서 만약 바닥에 닿은경우는 패스, 공중에 떠있는 경우중 열(세로)의 맨 밑은 공중에 떠있는 경우 이므로 옮겨야한다 미네랄에 닿거나 바닥에 닿을때까지 한칸씩 내린다. 이때 ㄷ 자 모양 주의 해야함. 소스코드

난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/2573 문제해결 아이디어 BFS를 사용해서 조건을 만족하는 빡구현 이였다. (내가 느끼기엔) 소스코드

난이도 : GOLD IV > 문제링크 : https://www.acmicpc.net/problem/14226 문제해결 아이디어 걸리는 시간의 최솟값을 구한다. 즉, 최단시간을 구해야하니 BFS로 풀면 된다. 3가지 연산만 사용해서 이모티콘을 S개 만든다 즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수c를 고려해서 풀면 된다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 복사 : (s,c) -> (s,s) 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 붙여넣기 : (s,s) -> (s+c, c) 화면에 있는 이모티콘 중 하나를 삭제한다. (s,s) -> (s-1, c) => 모든 연산은 1초가 걸리니 모든 경로의 가중치는 1이다. 따라서, dists + 1 과 같이 1을 더해줘야 한다. 소스코드

난이도 : GOLD V > 문제링크 : https://www.acmicpc.net/problem/16928 문제해결 아이디어 N개의 사다리의 (시작점, 끝점)과 M개의 뱀의 (시작점, 끝점)을 각각 graph에 넣어준다. bfs()를 수행하는데, 처음에 1번칸에서 시작하므로 q에 1을 넣고 시작한다. 현재 x번째 칸에서 k값을 더한 x+k가 다음칸이다. 다음 칸에 사다리나 뱀이 존재한다면 다음칸을 ladder나 snake로 바꿔준다. 소스코드

난이도 : LV 3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87694 문제해결 아이디어 사각형의 테두리를 graph에 1로, 내부와 외부는 0 으로 표시한다. 단위가 1씩 되면 길이 없더라도 graph에서는 붙어있는 것처럼 표현되기 때문에 전부 길이를 2배로 늘려준다. ex) 아래ㅐ 그림에서 3,5 와 3,6은 이어져있지 않지만 그래프내에서는 1이 연속해 있다. 그래프를 탐색하고 해당 이동거리에 // 2를 해준 값을 리턴 소스코드

난이도 : GOLD V > 문제링크 : https://www.acmicpc.net/problem/7569 문제해결 아이디어 평범한 BFS 문제. visited를 갱신할때 +1 더해가면서 날짜계산을 했다. 마지막에 안익은 토마토 있는지 확인하고 정답을 리턴. 소스코드

난이도 : LV 3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60063 문제해결 아이디어 다른사람의 문제풀이를 참고해서 풀었다. 최단경로 문제라서 BFS를 사용했다. 탐색을하면서 canMove 함수를 사용하여 회전, 이동이 가능한 경우를 리턴 canMove 함수에서 리턴 받은 경우들중 confirm(세트)를 통해 기존에 방문했는 지 확인한다. 방문하지 않은경우 confirm에 로봇의 좌표(두개)를 넣어주고, cnt+1을 하고 큐에 다시 넣어준다. 로봇중 한 부위라도 도착점에 도착하면 cnt를 리턴 소스코드

난이도 : LV3 > 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67259 문제 해결 아이디어 코너 생성여부를 어떻게 판단 할것인가 q에 x좌표 y 좌표 뿐만 아니라 어떤 방향으로 이동했는지 나타내는 direction 도 포함시킨다 dx, dy 값이랑 비교해서 같은 방향일 경우 +100, 다른방향일 경우 +600 각 좌표별 cost 값을 2차원 배열에 담을 것인가 3차원 배열에 담을 것인가 처음에 2차원 배열을 통해 문제를 풀었었는 데 테스트케이스 마지막 번호가 통과 되지않았다. 반례를 찾아보니 2차원 bfs 에서는 다음 q에 들어갈 nx, ny 가 같거나 작은 cost를 가질 경우에만 q에 추가를 했는데 이러면 nx,ny 에서 다음 지점이 코너인 경우와 직선인 경우 더 낮은 cost가 다음 지점에서는 더 높은 cost가 되는 경우가 생겼다. 3차원 배열

난이도 : GOLD I > 문제링크 : https://www.acmicpc.net/problem/13460 삼성 sw 역량 테스트 문제이다 문제해결 해결하지 못해서 다른풀이에서 영감 받았다. 파란공과 빨간공 bx,by rx,ry 로 저장한다. 구멍이나 벽을 만날 때까지 while True 로 움직인다. 파란구슬이 구멍에 빠지면 안되므로 그 경우는 continue로 넘긴다. 움직인 후의 빨간공과 파란공의 위치가 같다면 기존 위치에서의 차이로 값을 비교해서 정한다. 소스코드 배운점 visited 역시 graph 처럼 2차원 리스트로 표현 해야한다는 고정관념을 지우자. 순회할 때마다 depth를 증가시켜서 depth 값을 통해 return을 하는 경우는 dfs에서만 가능하다고 생각했었는데 이런 방식을 통해서도 bfs를 통해서도 depth를 구할수 있다는 점을 알게되었다.

난이도 : LV2 > 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199 문제해결 전형적인 bfs 탐색 문제에서 상하좌우 조건 부분만 수정한다. 상하좌우 탐색시 벽에 부딪히거나, 장애물을 만났을 경우까지 이동시킨다. visited 는 매번 움직일때마다가 아닌 위 조건을 충족했을 때에만 기록한다. 소스코드 from collections import deque dx, dy = [0,0,-1,1], [1,-1,0,0] def solution(board): n = len(board) m = len(board[0]) q = deque() cur = (0,0) for i in range(n): for j in range(m): if boardi == 'R': cur