[모의 테스트 풀이] N과 M(1)

2021. 1. 10. 21:45· Koala - 2기
목차
  1. 문제 1. N과 M(1)
  2. [백트래킹]
  3. [백트래킹 문제에 적용시키기 - 예제와 함께]
  4. [백트래킹 적용시키기 - 코드와 함께]

두번째 풀이를 시작하겠습니다!

문제 1. N과 M(1)

www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

백트래킹을 사용하여 풀 수 있는 문제입니다. 코드를 설명하기 앞서, 백트래킹이 무엇인지 살펴보겠습니다.

 

[백트래킹]

모든 경우를 방문하지만, 규칙을 가지고 방문하지 않아도 될 노드는 방문하지 않는 알고리즘입니다. 해당 노드의 답이 될 수 있는 가능성을 따져보고,  답이 될 수 있는 가능성이 있다면 계속 진행, 그렇지 않다면 부모노드로 돌아가 탐색을 계속합니다. 

우리는 이미 이 알고리즘을 잘 알고 있습니다. 위의 설명이 이해가 되지 않으신다면, 다음과 같은 예제는 어떤가요?

 

친구와 오목을 하고 있다고 생각해 봅시다.

당신은 흰돌, 친구는 검은돌입니다.

그런데...

앗... 검은 돌이 대각으로 3개를 만들었는데 내 이익에 눈이 멀어 놓치고 말았습니다. 꼼짝없이 지게 생겼죠.

하지만 당신은 힘이 친구보다 힘이 셉니다.

 

당신: 야 한번만 무르자...

친구: 아 응...

 

뒤로 되돌아가 아까했던 실수를 반복하지 않고 최적의 수를 찾았습니다. 결국 친구가 이길것 같긴 하지만, 그때마다 무르면 됩니다. 앞으로 누구도 당신과 오목을 하고 싶어하지 않을거에요. 하지만 괜찮습니다. 이기면 장땡입니다.

 

우리는 백트래킹을 대충 알 것 같습니다. 그럼 이 문제에 백트래킹을 어떻게 적용시킬지 살펴보겠습니다.

 

[백트래킹 문제에 적용시키기 - 예제와 함께]

N=3, M=3이라고 가정하겠습니다.

우리는 3칸짜리 출력을 해야 하므로 다음과 같이 태초에 빈 세칸짜리 네모가 있다고 생각해봅시다.

 

 

왼쪽부터 차례대로, 문제가 요구했던 것 처럼 숫자를 채워보겠습니다. 언제까지? 세칸이 모두 다 찰때까지요. 다음과 같이 트리가 꽉 차면, 당신은 결정해야합니다.

우선 123의 목표는 채웠으니 출력합니다(대부분의 코딩 테스트에서, 출력이 생길때마다 출력해도 괜찮습니다!). 

다만 세칸을 모두 채웠으므로, 부모에게 돌아가 새로운 자식을 만들 수 있는지 물어봅니다. 하지만 12□(부모노드)의 입장에서는 더이상 해줄게 없습니다. 부모의 부모 노드로 올라가 자식을 만들어봅니다.

다음과 같은 과정을 통해, 우리는 132를 또 출력할 수 있었습니다. 그럼 우리는 맨 앞 숫자가 1인 모든 경우의 수를 출력한 것 같습니다. 그럼, 맨앞 노드가 2인 경우에도, 3인 경우에도 모든 수열을 출력할 수 있지 않을까요? 그럼 코드를 살펴보겠습니다(트리 다 그리기 귀찮은거 아닙니다).

 

[백트래킹 적용시키기 - 코드와 함께]

#include <iostream>
using namespace std;

int n, m;
int field[9], visited[9] = { 0, };

void back_tracked(int num);
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	back_tracked(0);
	return 0;
}

void back_tracked(int num)
{
	if (num == m)
	{
		for (int i = 0; i < m; i++)	cout << field[i]<<" ";
		cout << "\n";
		return;
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = 1;
				field[num] = i;
				back_tracked(num + 1);
				visited[i] = 0;
			}
		}
	}
}

제가 변수명 짓는 센스가 없습니다...

field는 위에 그림에서 설명한 빈 칸과 같습니다.

visited는 어떠한 숫자 혹은 배열을 방문 했었는지 잠시 기억하는 배열입니다. 자주쓰이니, 알아두시면 좋은 스킬입니다.

 

main입니다. 위에 두 줄은, 무시하셔도 됩니다. 출력이 어마무시하게 많거나 입력이 많을 경우 넣어주는 코드입니다.

 

n과 m을 입력받아 바로 back_tracked함수에 인자 0을 넣어주는 모습을 볼 수 있습니다.

그림을 그려보며 직접 visited와 field의 변화를 썼다 지우며 코드가 돌아가는 모습을 확인해보세요.

간략하게 설명하자면,  첫번째 if(cnt==m)부분에서 빈칸이 모두 채워졌는지 확인하고, 자신을 부른 함수에 재귀적으로 돌아가 마지막 원소가 채워지기 직전의 상태로 되돌아가게 됩니다. 

 

그럼, 다음 문제로 가볼까요??

'Koala - 2기' 카테고리의 다른 글

[모의 테스트 풀이] 랜선 자르기 & 수 찾기  (0) 2021.01.10
[모의 테스트 풀이] 유기농 배추  (0) 2021.01.10
[모의 테스트 풀이] RGB거리  (0) 2021.01.10
[모의 테스트 풀이] 분수찾기  (0) 2021.01.10
[BOJ] 14565번. 역원(Inverse) 구하기  (0) 2021.01.04
  1. 문제 1. N과 M(1)
  2. [백트래킹]
  3. [백트래킹 문제에 적용시키기 - 예제와 함께]
  4. [백트래킹 적용시키기 - 코드와 함께]
'Koala - 2기' 카테고리의 다른 글
  • [모의 테스트 풀이] 유기농 배추
  • [모의 테스트 풀이] RGB거리
  • [모의 테스트 풀이] 분수찾기
  • [BOJ] 14565번. 역원(Inverse) 구하기
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • BOJ
  • C++
  • 백준
  • dp
  • 백트래킹
  • 파이썬
  • dfs
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[모의 테스트 풀이] N과 M(1)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.