신입사원 현재의 개발일기

- 문제 링크 https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n

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/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제의 핵심은 방문 여부를 체크하는 visited을 3중 배열로 만들어야 한다는 것이다. 그래야 벽을 부순 횟수의 파악이 수월하다. 나도 이 아이디어를 생각해내는 데 많은 시간이 걸렸다. ㅠㅠ 최단경로로 가는 길에 벽이 있다면 단 한 번만 부시고 계속 이동하면 된다. 더 자세한 풀이는 주석을 참고하면 된다. import sys input = sys.stdin.readlin..

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 = [..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 말 그대로 최단거리를 구하면 되는 어렵지 않은 문제였다. bfs를 돌면서 새로 방문하는 곳인 graph[nx][ny]에 현재 위치 값인 graph[a][b]에 1을 더해 거리를 더한다. bfs가 끝나고 for문을 돌며 graph[i][j]의 값이 1일 때와, 해당 위치를 방문하지 않았다면 graph[i][j]의 값을 -1로 바꾼다. import sys ..