https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 개요 - 1, 0과 같은 단순한 원소들로 이루어진 전형적인 자료구조를 탈피한 첫 번째 문항인 것 같다. 따라서 추가적인 조건문의 계산만 더해주면 되므로 사실상 그리 복잡하지는 않다. - dfs 함수에 부가적인 기능을 넣고 싶지 않아서 답을 도출하는 이중 for문을 조금 길게 작성했다. - 재귀를 이용하는 dfs에 약하다고 판단해서 스택은 고려하지 않고 푸는 중인데, 맞은 사람 중 런타임이 ..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 개요 - dfs/bfs 형 기본 문제. 차별점은 숫자로 구성된 리스트가 아니라 알파벳 리스트이기 때문에 아스키 코드를 사용해야 효율성이 높아진다는 정도. - [0][0] 값에서부터 dfs를 돌면서 거리값을 갱신한다. 재귀를 통해서 갈 수 있을 만큼 들어가기 때문에, dfs 루프가 끝나는 시점이 하나의 경우의 수가 된다. - answer값을 갱신하는 방법은 구글링으로 참고했다. 아주 조금만 ..
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 개요 어제 포스팅했던 트리의 지름과 똑같은 문항이다. input의 형식이 조금 바뀌어서 index와 관련해 생각할 부분이 늘어났지만 그 외의 풀이는 차이가 없다. 이전에 BFS로 문제를 해결했어서, 이번엔 DFS로 접근해봤는데 visit리스트의 리셋이나 변수들의 유효 범위 등 고려할 것들이 많아져 결국 포기. 추가로 우수 풀이 중 BFS/DFS가 아닌 괜찮은 접근의 풀이가 있어 소..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 개요 트리 알고리즘 문항이긴 하나, 해결법은 BFS다. 트리를 정리하는 자료구조로 보통 리스트나 딕셔너리가 사용되는 건 알고 있었는데, 문제별로 그 구조를 조정할 필요는 있을 듯하다. 사실 처음 문제 풀 때 꽤 어렵게 접근해서 쩔쩔매긴 했는데, BFS를 두번 진행한다는 식의 발상은 못했다 아이디어 - BFS를 이용하여 루트 노드(1)부터 탐색을 진행한다. 가장 큰 가중치를 갖는..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 휴가 직전은 항상 번아웃이 오는 것 같다. 번아웃이라는 단어로 삶을 대체하기엔 그리 치열하게 살지는 않았던 것 같아서 부끄럽지만, 사람은 핑계의 산물 아니겠는가. 어쨌든 여러 핑계를 뒤로하고 오늘부터 다시 1일 1 알고리즘 체재로 포스팅하지 않을까 싶다. 익숙한 BFS/DFS 문항들은 이제 가닥만 조금 잡히면 구현하는 데에 있어서는 크게 문제 되지 않는 거 같다. # PYTHON CODE (..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이쪽 문제들은 왜 이렇게 변태 같을까. 진짜 고생했다. 한발 다가가면 두발 멀어지는 놈들이다. 어제 유튜브 알고리즘에 켠 김에 백준 루비 티어 찍는다는 컨셉의 영상도 있더라... 나도 변태 같은 개발자가 되어야겠다. BFS로 접근해야하는 이유는 같은 레벨일 때(걸린 시간이 같을 때)의 케이스들을 따져야 하기 때문이다. # PYTHON CODE (1) from collec..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 무려 7번이나 시간 초과가 발생해서 머리가 터질뻔했다. 답은 의외로 단순한 곳에 있긴 했는데, queue 사용 시, deque모듈을 쓰지 않은 것이 원인이었다. 이 문제가 BFS인 이유는 총 걸린 시간을 구해야 한다는 점과 익은 토마토가 여러군데에 심어져 있다는 점으로 보았을 때, 같은 레벨에 위치한 노드들부터 살피면서 나아가는 탐색이기 때문이다. 처음 추구한 방향은 한 큐가 끝날..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS알고리즘으로 접근했을 때 계속 인덱스 에러가 나서 고생했다. # PYTHON CODE (1) - DFS import sys sys.setrecursionlimit(2500) t = int(sys.stdin.readline()) def dfs(a, b): if a = n or b = m: return False if tree[a][b] == 1: tree[a][b] = ..
