반응형
snowman95
코딩수련장
snowman95
전체 방문자
오늘
어제
  • 분류 전체보기 (229)
    • 앱테크 (3)
    • 옵시디언 (5)
    • 드라마, 영화 (1)
    • 개발자 이야기 (23)
    • 프로젝트 (10)
      • 프로젝트 방법론 (7)
      • 프로젝트 기록 (2)
      • Github (1)
    • 개발 지식 (0)
      • 디자인 패턴 (0)
    • 프론트엔드 개발 (5)
      • 테크트리 (2)
      • React.js (19)
      • ReactNative (2)
      • Next.js (6)
      • GraphQL (6)
      • 패키지 매니저 (2)
      • 라이브러리 (3)
      • 상태관리 라이브러리 (4)
      • Web 지식 (3)
      • HTML CSS (26)
      • Javascript (16)
      • 도구 (Tool) (3)
      • 성능 최적화 (1)
      • 디자인시스템 (0)
    • Python (53)
      • 모음집 (1)
      • 문법 (12)
      • 라이브러리 (15)
      • 알고리즘 (10)
      • 백준 문제풀이 (9)
      • 코딩테스트 (2)
      • 도구 (Tool) (3)
    • C++ (20)
      • 알고리즘 (6)
      • 삼성SW기출 (6)
      • 삼성 A형 (6)
    • 데이터사이언스 (1)
    • 인프라 (9)
      • 하드웨어 지식 (4)
      • Ansible (2)
      • Database (2)
      • 쉘스크립트 (1)
    • 주식 (0)
    • 취업 준비 (4)
      • 취업 이야기 (0)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • 나의 해방일지
  • Next.js #graphql #tailwind.css
  • C++
  • 전공 요약 #데이터베이스
  • 면접
  • 삼성SDS
  • 티스토리챌린지
  • 기계식키보드 #nuphy
  • 언어
  • 전공 요약 #운영체제
  • 전공요약
  • GraphQL
  • 오블완
  • 삼성SW역량테스트
  • A형
  • 전공 요약 #네트워크
  • 알고리즘
  • nextjs
  • 공간복잡도
  • 백준

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
snowman95

코딩수련장

[백준 17070: 파이프 옮기기 1] (C++)
C++/삼성 A형

[백준 17070: 파이프 옮기기 1] (C++)

2019. 10. 21. 02:01
728x90
반응형

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ파이프 옮기기 1

          https://www.acmicpc.net/problem/17070

 

 

l 문제

 

1. 유현이가 새 집으로 이사했다.
새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다.
각각의 칸(r, c)은 1부터 시작하며 빈 칸이거나 벽이다.
빈 칸은 0, 벽은 1로 주어진다.
2. 집 수리를 위해서 파이프 하나를 밀어서 이동시키려고 한다.
파이프는 →, ↘, ↓ 방향으로 밀 수 있다.
파이프는 밀면서 45도 까지 회전시킬 수 있으며, (→, ↘, ↓) 3가지 방향이 가능하다.
3. 놓여진 방향에 따라 이동 방법은 다음과 같다.
가로 : →, ↘
세로 : ↘, ↓
대각선 : →, ↘, ↓
4. 파이프를 놓을 때 색칠된 부분은 반드시 빈 칸( 0 )이어야 한다.
하나의 파이프는 2개의 연속된 칸을 차지한다.
가장 처음에 파이프는 ( 1, 1 )와 ( 1, 2 )를 차지하고 있고, 방향은 가로이다.
( 1, 1 )와 ( 1, 2 )는 빈 칸이다.


 

 

l 연산 순서

 

1. 모든 진행 가능한 방향으로 파이프를 민다.






2. 파이프가 ( N, N ) 위치에 도달하면 Count 증가

 

 

l 예시

 

시작 모습 3
P P 0
0 0 0
0 0 0
대각선 3
P P 0
0 0 P
0 0 0
아래 3
P P 0
0 0 P
0 0 P

 

 

l 입력

 

첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 
둘째 줄부터 N개의 줄에는 집의 상태가 주어진다.
빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

 

 

l 출력

 

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다.
이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

 

 

l 풀이

 

DFS로 풀 수 있다.
DFS 함수
{
   for (가능한 방향들)
   {
      1. 범위 조건 검사
      2. 파이프를 놓는다.
   }
}
방향에 따라 놓을 수 있는 모든 방향으로 파이프를 계속 놓으면서 탐색
일일이 switch나 if문을 써서 제어하는 것 보다
전역으로 가능한 방향을 미리 선언해두면
쉽고 깔끔하게 코드를 작성할 수 있다.

 

 

l  코드

 

#include<iostream>
#include<vector>
using namespace std;

int N, home[17][17], ans;
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
vector<int> action[3] = { {0,2}, {1,2}, {0,1,2} };

// type 0 : 가로, 1 : 세로, 2 : 대각
void recur(int x, int y, int type)
{
	for (auto &t : action[type])
	{
		int tx = x + dx[t];
		int ty = y + dy[t];

		if (tx < 1 || ty < 1 || tx > N || ty > N || home[tx][ty])
			continue;

		if (t == 2 && (home[tx - 1][ty] || home[tx][ty - 1]))
			continue;

		if (tx == N && ty == N)
		{
			++ans;
			continue;
		}

		recur(tx, ty, t);
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> home[i][j];

	if(!home[N][N]) recur(1, 2, 0);

	cout << ans;
	return 0;
}

 

반응형
저작자표시 (새창열림)

'C++ > 삼성 A형' 카테고리의 다른 글

[백준 17406: 배열 돌리기 4] (C++)  (0) 2019.11.15
[백준 17281: 야구] (C++)  (0) 2019.10.31
[백준 17136: 색종이 붙이기] (C++)  (0) 2019.10.21
[백준 17135: 캐슬 디펜스] (C++)  (0) 2019.10.21
[백준 16637: 괄호 추가하기] (C++)  (0) 2019.10.21
    'C++/삼성 A형' 카테고리의 다른 글
    • [백준 17281: 야구] (C++)
    • [백준 17136: 색종이 붙이기] (C++)
    • [백준 17135: 캐슬 디펜스] (C++)
    • [백준 16637: 괄호 추가하기] (C++)
    snowman95
    snowman95
    (17~19) Unity/Unreal Engine 게임 프로그래머 (20~21) System Administrator ___________ (22~) React 웹 프론트앤드 개발자 __________ 깃헙 : https://github.com/snowman95

    티스토리툴바