원래 시작점 위치 (2인 곳)을 따로 찾아서 시작점으로 넣어줘야 할 것 같은데 모든 예제의 시작점이 같길래 그냥 (1,1)로 넣어줬다. 만약 다른 테스트 케이스도 돌리는 거라면 시작점도 따로 변수에 담아줘야 할 것이다. D4지만 가장 간단한 bfs예제였다. 끝나는 경우는 3인 곳을 끝까지 만나지 못한 경우를 flag변수의 false로 하여 조건 출력해주면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static int t; static int[][] map; static int[] xpos= {0,0,1,-1}; static int[] ypos= {1,-1,0..
dfs로 풀면 효율성 시간 초과가 난다. 최단 거리인 경우 bfs로 모든 경우의 수를 구할 경우에는 dfs 문제로 많이 갈리는 것 같다. function solution(maps) { let xpos=[0,0,1,-1]; let ypos=[1,-1,0,0]; var answer = -1; const q=[[0,0,1]]; while(q.length!=0){ let y=q[0][0]; let x=q[0][1]; let cnt=q[0][2]; q.shift(); if(y===maps.length-1 && x===maps[0].length-1){ answer=cnt; break; } for(let i=0;i
www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net vis 배열을 3차원으로 만들고 세 번째 인자 c가 1이면 뚫은 벽, 아니면 뚫지 않은 벽이다. 벽을 뚫을 필요가 없을 때는 일반적인 bfs를 해주고 이미 한번 뚫은 뒤에는 (c가 1인채로 온 경우에는 현재 위치가 0인 경우에만 지나갈 수 있다) 벽을 뚫을 경우에는 현재 위치가 1(벽)이고 c가 0인 경우이다. import sys input=sys.stdin.readline from c..
www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 방향 회전에 후진할 경우 이동방향, 회전할 경우 이동방향을 계산해서 이동시킨다 # 북동남서 0 1 2 3 -> 후진: 2 3 0 1 # 북동남서 0 1 2 3 -> 회전: 3 0 1 2 from _collections import deque n,m=map(int,input().split()) vis=[[0]*m for _ in range(n)] r,c,d=map(int,input().split()) a=[li..
www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net from collections import deque n,m,k=map(int,input().split()) dx,dy=[1,-1,0,0],[0,0,1,-1] vis=[[-1]*m for _ in range(n)] a=[list(input()) for _ in range(n)] x1,y1,x2,y2=map(int,input().split()) q=deque() q.append((x1-1,y1-1)) ..
www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net from _collections import deque def bfs(): q = deque() q.append((i,j,0)) vis[i][j]=1 while q: y,x,cnt=q.popleft() if a[y][x]==1: return cnt for k in range(8): xx=x+dx[k] yy=y+dy[k] if xx=n: continue if vis[yy][xx]: c..
www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net from collections import deque from collections import defaultdict n=int(input()) time=defaultdict(int) q=deque() # 화면, 클립보드 개수 q.append((1,0)) time[(1,0)]=0 while q: s,c=q.popleft() if s==n: print(time[(s,c)]) exit() # 클립보드에 복사 fo..
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 계속 메모리 초과가 났는데, 이전에 지나온 위치를 계산할 때 무한 반복되는 구간이 있어 -1로 초기화해줄 필요가 있었다 path[N]=-1로 출발위치만 초기화해주면 된다 from collections import deque from collections import defaultdict N, K = map(int, input().split()) MAX_SIZE = 1000..
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 2보다는 쉽다 더 짧게 갈 수 있는 경우 (check)를 더 작게 업데이트 해주자 from collections import deque N, K = map(int, input().split()) MAX_SIZE = 100001 q = deque() q.append(N) check=[-1]* MAX_SIZE check[N]=0 while q: x = q.popleft() i..
www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 1. 아직 완전히 이해하지는 못했는데 cnt는 방법의 수이고 check는 현재위치에서 걸린 시간이다 y는 x에서 이동할 수 있는 곳을 나타내는데 y의 시간이 x에서 한 번 이동하게 되는 시간이랑 같거나 처음 방문한다면 경우의 수를 더해주기 위해 큐에 넣어주면 된다. from collections import deque N, K = map(int, input().split..