본문 바로가기

code/BOJ

 (63)
백준 9944 NxM 보드 완주하기 9944번: NxM 보드 완주하기 문제 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다. 게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 www.acmicpc.net /* 1시간 55분 이상 소요 */ /* 1. map의 첫번째 칸은 이미 입력됐으므로 두번째 칸부터 입력받기, row는 첫번째 칸부터 참조 */ /* 2. if(map)의 역할을 while(..
백준 2933 미네랄 2933번: 미네랄 문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 www.acmicpc.net /* 1시간 32분 소요 */ /* 1. map indexing 오류 : 바닥은 0이 아니라 R - 1 */ /* 2. DFS 실행 조건 누락 */ /* 3. 몇 칸 내릴 수 있는지 제대로 세기 위해서는 ..
백준 3568 iSharp 3568번: iSharp 문제 선영이는 C, C++, Java와는 다른 아주 세련된 언어를 만들었다. 선영이는 이 아름답고 예술적인 언어의 이름을 i#으로 정했다. i#은 기본 변수형과 배열([]), 참조(&), 포인터(*)를 제공한다. 배열, 참조, 포인터는 순서에 상관없이 혼합해서 사용할 수 있다. 즉, int의 참조의 참조의 배열의 포인터도 올바른 타입이다. int&&[]* i#은 여러 개의 변수를 한 줄에 정의할 수 있다. 공통된 변수형을 제일 먼저 쓰고, 그 다음에 각 www.acmicpc.net 아직 string 사용이 미숙한 것 같다. 선배님의 코드가 굉장히 세련됐다고 느꼈는데, 입력받은 문자열에 대해 strtok를 수행하고 문자열을 뒤집을 때도 stack의 특성을 활용했기 때문이다. /* ..
백준 2290 LCD Test 2290번: LCD Test 문제 지민이는 새로운 컴퓨터를 샀다. 하지만 새로운 컴퓨터에 사은품으로 온 LC-디스플레이 모니터가 잘 안나오는 것이다. 지민이의 친한 친구인 지환이는 지민이의 새로운 모니터를 위해 테스트 할 수 있는 프로그램을 만들기로 하였다. 입력 첫째 줄에 두 개의 정수 s와 n이 들어온다. (1 ≤ s ≤ 10, 0 ≤ n ≤ 9,999,999,999)이다. n은 LCD 모니터에 나타내야 할 수 이며, s는 크기이다. 출력 길이가 s인 '-'와 '|'를 이용해서 www.acmicpc.net 지난 코드로부터의 개선: 이전 코드(12546935)처럼 문자/공백 여부를 bool로 저장하면 메모리는 절약할 수 있지만 bool값을 읽어와서 매번 문자를 쓸지 공백을 쓸지 분기가 발생해서 속도가 ..
백준 14502 연구소 설계: '감염 영역' BFS를 통해 얻는 건 '안전 영역'의 여집합의 크기이기 때문에 해당 집합을 칭하는 '감염 영역'이라는 개념 도입 BFS를 수행할 때 벽(1)의 개수는 고정이기 때문에 '안전 영역'(0)의 최대화는 '감염 영역'(2)의 최소화임 trimming BF에서 현재까지 최소 감염영역의 크기(ma)를 BFS의 인자로 넘겨주고, BFS 중 감염영역이 ma 이상이 되면 어짜피 ma 갱신이 불가함으로(정답에 영향 주지 않음) 탐색 중지 0의 좌표를 배열화 BF body의 for문으로 2차원인 map을 커버하려면 1. '1일 경우 skip', 2. r과 c 모두 인자로 유지하면서 'c가 C - 1이 되면 ++r, c = 0'의 예외처리를 해줘야 한다. BF는 시간 복잡도((R X C)!)가 높기 때..
백준 5213 과외맨 설계: BFS 조건 만족시키기(mapping) BFS의 '비용=1' 조건을 만족시키기 위해 주어진 조각들의 map(pm)을 타일의 map(ts)에 대응시키기 pm(idx = 조각 위치, pm[idx] = 조각번호), tn(idx = 조각 위치, tn[idx] = 타일번호) 2조각이 1타일에 대응되므로 pm과 동일한 크기의 tn배열 선언, 첫 2칸을 1로하고 2칸마다 1씩 증가 pm상 모든 조각에 대해 2조각 씩 뛰어넘으며 이웃 조건 검사해 adj list 구성 ts(idx = 타일번호, ts[idx] = 타일의 이웃 목록 => graph repr; adj list) 수정: 경로 출력하기 qnode를 임의 메모리에 선언x 타일번호 tn으로 접근할 수 있도록 tn을 idx로 삼는 qnode 배열 선언 qs(..
백준 3184 양 설계: map상 obj인 울타리, 양, 늑대의 존재여부를 나타내는 bool 2차원 배열 선언 vs map 2차원 배열 선언 전자는 한 위치에 여러 obj 존재 가능할 경우 유용 vs 후자는 한 위치에 하나의 obj만 존재 가능할 경우 유용 수정: 탐색시 '기방문 위치 skip' 누락 switch의 각 case별 break 누락 소요시간: 개선: 방문 여부를 나타내는 별도 배열 선언 대신 map에 '#'로 표시 map상 모든 위치에 대해 탐색하는 대신 'o', 'v'가 존재하는 위치만 탐색 // BFS버전 #include #include #include using namespace std; int dr[] = { -1, 0, 1, 0 }; int dc[] = { 0, 1, 0, -1 }; #define I..

티스토리툴바