Leta Learns

문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 자기 자신과의 단계는 0이므로 이를 표현하기 위해 visited의 초기값을 -1로 지정하였다. bfs함수를 호출하면 해당 사람(?)의 visited 값을 0으로 바꾸어준다. (자기자신) 한 번 방문할 때마다 이전에 방문한 친구의 단계에서 1을 더해준다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합이므로 bfs 함..

문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net bfs 풀 때 visited 배열 안 쓰고 푸는 게 편하길래 이 문제도 그렇게 접근했는데 잘 안 풀려서 결국 visited 배열을 사용하였다. 모든 L에 대해서 bfs 탐색을 시도해야 해서 시간초과 날까봐 코드 짤 때부터 걱정했는데 역시나였다. pypy3로 제출해서 성공하였다. import sys from collections import deque input = sys.stdin.readlin..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 단순 bfs 였다. 이제 그래프는 잠시 쉬어도 될 것 같은 느낌.. import sys from collections import deque input = sys.stdin.readline def bfs(cur_y, cur_x): chess[cur_y][cur_x] = 1 q = deque() q.append((cur_y, cur_x)) while q: y, x = q.popleft() if ..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 항상 dxdy 기법에 익숙한 bfs를 dxdy 없이 그냥 큐로 구현하는 것 빼고는 어렵지 않은 문제였다. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문해야 해서 인접리스트를 sort 해주어야 했는데, 왠지 당연히 입력할 때부터 제대로 정렬해서 줄 것 같다는 근거 없는 생각에 sort를 안 해서 틀렸다. 입력받으면서 각각의 인접리..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 골드라서 좀 겁먹었었는데 무난한 그래프 문제였다. 그리드에 색 입력 받을 때 'R', 'R', 'R', 'B', 'B' 이런 식으로 되어야 하는데 자꾸 'RRRBB' 이렇게 받아져서 그 부분 조금 헤맸다. 색약이 아닌 경우를 먼저 구하고, 'R'을 'G'로 바꾼 후 색약인 경우를 구한다. ('G' -> 'R'도 가능) 이때 visited 초기화 해주어야 하는 것 잊지 말기. impor..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 아 아래가 0이고 위가 m, n이라서 인덱스 정리 다 해주어야 하는 줄 알고 한참 헤맸었는데 생각해보니까 굳이 인덱스 안 바꿔주어도 되는 문제였다. 영역만 구하면 되는 거니까 그림이 뒤집혀 있어도 상관 없었기 때문에.. 쨌든 그거 해결하고 나니 순조로웠다. bfs 함수 만들 때 자동적으로 가장 마지막 (n, m)인 경우 break를 넣어주었더니 여기서 에러가 났다. : b..

문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 박스에 맥주를 최대 20개 까지 담을 수 있고, 50m에 맥주 한 병씩을 마셔야 한다. => 노드들 간의 거리가 1000m를 넘어서는 안 된다. 문제가 복잡해보이게 적혀있어서 그렇지 이것만 이해하면 나름 괜찮았던 것 같다. 입력 받는 부분에서 1차로 막혔었는데 편의점이 n개라서 for문을 n+2로 돌려서 입력값 전체를 다 받으려고 했었다. 다시 보니까 편의점 n개만 for문으로 돌리고 ..

문제를 처음 봤을 때 이해가 가지 않아서 무슨 말인지 한참을 읽었다. 우선 50m마다 맥주를 마셔야 하고, 맥주는 20개 씩 들고 갈 수 있다는 말이 노드와 노드 사이의 거리가 1000m가 넘어서는 안된다는 뜻임을 캐치해야 했다. 그 후에는... 누가누가 코드로 잘 만들어내느냐.... dxdy기법 안 쓴 bfs 문제 오랜만이라 재밌고.. 어려웠다. import sys from collections import deque input = sys.stdin.readline def bfs(): q = deque() q.append([home[0], home[1]]) while q: x, y = q.popleft() if abs(x - fest[0]) + abs(y - fest[1])

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 확실히 여러 번 푸니까 이제는 문제 접근법이 비교적 쉽게 생각난다. 물론 실버인 것도 한 몫했겠지만... ㅋㅋㅋ 보통 m=row, n=col으로 하는데 여기서는 m=col, n=row여서 헷갈렸다. 그것때문에 배열 인덱스를 몇 번이나 바꿔서 재실행했는지 모르겠다. ㅠㅠ 그 부분 빼고는 무난한 문제였다고 생각한다. import sys input = sys.stdin.readline from collecti..

#DFS 탐색 - 그래프 탐색 https://www.codetree.ai/missions/2/concepts/4/problems/graph-traversal/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai import sys input = sys.stdin.readline def dfs(v): visited[v] = 1 for i in range(len(adjList[v])): w = adjList[v][i] if not visited[w]: dfs(w) n, m = map(int, input().split()) adjList = [[] for i in range(n+1)] visited = [0 for i in range(n+1)] for i in ran..