https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 1. 반복문 문제 느낌이 진실을 아는 사람이 좀비같이 감염시키는 것이라 생각 그래서 진실을 아는 사람과 같이 있는 사람들을 진실을 아는 사람으로 바꿨다. 근데 이러면 진실을 아는 사람들이 바뀌어서 전체 파티를 또 탐색해야 하고 이를 계속 반복해야 해서 실패했다. 2. 그래프 그러다가 동시에 한 번에 해야 된다는 것을 깨닫고 그래프를 사용하기로 결정 각 파티마다 있는 사람들을 두 명씩 양방향으로 이어..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 아이디어 1. bfs 주사위를 선택(1 ~ 6)할 수 있는 점과 최단 횟수를 구해한다는 점에 bfs를 선택 뱀과 사다리만 잘 체크해주면 되는 문제. 코드 설명 deq = deque() deq.append([1, 0]) visited[1] = True while deq: po, count = deq.popleft() if po == 100: print(..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 아이디어 1. bfs 최소한의 명령 어을 출력 하라 했으므로 bfs가 아니면 못 풀 거 같다고 생각했다. 시간제한도 6초로 넉넉하게 있어서 충분하다고 생각했다. 2. 시간 초과 요즘 계속 시간 초과가 뜬다. 6초라서 넉넉할 줄 알았는데. 시간 초과가 뜬이유는 다음과 같다. D, S, L, R 각각의 명령어를 간소하게 구현해야 했는데, if문이나 리스트를 사용해 시간제한이 걸린 거 같다..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 아이디어 1. 파이썬 이슈 처음에 dfs로 접근했는데 Python3로 채점하면 80% 에서 시간 초과가 발생했다. (pypy로는 통과) 포기하고 bfs로 접근했는데 또 시간 초과가 발생해서 조건을 몇 개 추가하니 통과됨. c++ 였으면 dfs로 통과했을 거 같다. 2. 구현 파트는 크게 두 개로 나눴다. 국경선 열기 인구수 분배 코드 설명 기본적으로 이중 for문을 사용해서 각 위치..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 미로 찾기랑 비슷하다. 저번에 탐색 문제 풀 때 bfs로 시간 초과가 뜬 경험을 삼아 dfs로 풀었는데 해결이 안 됐다. 생각해보다가 bfs로 풀었는데 바로 답이 나왔다. 내 생각에는 bfs니까 자연스럽게 최단거리가 나오니까(depth 별로 탐색) 이런 문제는 bfs로 푸는 게 좋은 거 같다. 풀이 과정 dx = [2,2,1,1,-1,-1,-2,-2] dy = [1,-1,2,-2,2,-2,1,-1]..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 과정 저번에 푼 토마토 문제와 거의 유사하다. 차이점은 z축이 생김. 문제에서 M,N,H 최대값이 모두 100으로 큰수가 아니여서 그냥 3차원 배열을 사용하기로 했다. 따라서 z축 관련된 부분만 이전 문제에 추가하면 된다. 이전 문제 풀이에 대한 정보는 7576-토마토 참조 import sys from collections import deque input = sys...

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 과정 1697 - 숨바꼭질 문제와 비슷하다. 차이점은 숨바꼭질 3 문제는 순간이동할 때 0초 소요된다. 숨바꼭질 문제를 예전에 풀어서 날로 먹으려 순간이동 부분만 코드를 수정했는데 틀렸다. 다시 짜야하나 싶었는데 조금만 수정하니까 해결됐다. bfs로 해결함. from collections import deque N , K = map(int,input().sp..