신입사원 현재의 개발일기

- 문제 링크 https://www.acmicpc.net/problem/2589 - 풀이 bfs로 풀었다. 문제를 보면 알겠지만 범위 내에서 모든 육지를 다 체크해야 하는 완전 탐색 문제이다. 코드를 보면 알겠지만 그냥 bfs에서 사알짝 응용 버전이다. 별로 어렵지 않았다. 근데 정답률이 37% 밖에 되지 않아서 조금 이상하긴 했다. - 코드 import sys from collections import deque input = sys.stdin.readline dx = [0,0,-1,1] dy = [-1,1,0,0] def bfs(x, y): visited = [[0] * M for _ in range(N)] queue = deque() queue.append((x, y, 0)) visited[x][y..

- 문제 링크 https://www.acmicpc.net/problem/1012 - 풀이 그래프를 가로 x 세로 만큼 먼저 선언해놓고, K만큼 배추의 위치를 입력받을 때 graph 배열에 배추의 위치를 1로 표시한다. 그리고 배추가 있는 곳에서 bfs를 돌려주면 된다. 밑에 코드를 보면 알겠지만 배추의 위치를 입력받을 때 a, b 위치만 바꿔주는 것만 고려하면 특별히 예외처리 해줄만한 것도 없어서 푸는데 한.. 7분 걸렸던 것 같다. bfs를 한 번 실행할 때 마다 배추흰지렁이가 1마리씩 필요하다고 생각하면 편하다. - 코드 import sys from collections import deque input = sys.stdin.readline dx = [0,0,-1,1] dy = [-1,1,0,0] d..

https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 쇼미더 코드에서 나온 은근 재미있는 문제였다. 보통의 bfs 알고리즘을 통한 그래프 탐색은 0과 N, M 사이의 범위 안에서만 탐색을 했는데, 이 문제는 범위가 없고 nx, ny가 끝 지점에 다다랐을 때 다시 처음 지점으로 이동시키면 되었다. 문제 자체는 어렵지 않고, 기본 bfs에서 조금만 응용하면 되는 문제이다. 코드를 보면 이해가 빠를 것 같다. import sys from col..

https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 이 문제는 조합(combinations)을 사용해서 풀어야 하는 문제였다. 그러나 나는 써본 적이 없어서 이걸 어떻게 풀어야 하나 1시간 가량 고민하다가 풀이를 참고해서 풀었다. 자세한 설명은 코드에 주석을 달아놨으니 참고하면 된다. import sys from collections import deque from itertools import combinations input = sys.stdin.rea..

https://www.acmicpc.net/problem/18405 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net BFS 알고리즘을 사용해서 해결할 수 있다. 낮은 번호부터 전염되는 조건을 확인하기 위해 먼저 배열에 넣고 sort를 해준 뒤 배열을 deque로 변환했다. import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) graph = [..