#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;
typedef long long ll;
const int INF = 1000'0000;
vector<pair<int, int>> adj[505];
int n, m, w;
int d[505];
bool bf()
{
fill(d, d + 505, INF);
d[1] = 0;
//n - 1번 동안 모든 간선을 확인해가며 최소 비용을 계산한다.
for (int i = 0; i < n - 1; i++)
{
for (int j = 1; j <= n; j++)
{
for (auto nxt : adj[j])
{
d[nxt.first] = min(d[nxt.first], d[j] + nxt.second);
}
}
}
//음수 사이클이 존재하는지 확인한다.
for (int j = 1; j <= n; j++)
{
for (auto nxt : adj[j])
{
if (d[j] + nxt.second < d[nxt.first]) return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> m >> w;
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < m; i++)
{
int s, e, t;
cin >> s >> e >> t;
adj[s].push_back({ e, t });
adj[e].push_back({ s, t });
}
for (int i = 0; i < w; i++)
{
int s, e, t;
cin >> s >> e >> t;
adj[s].push_back({ e, -t });
}
cout << (bf() ? "YES" : "NO") << '\n';
}
}
처음에는 c++ string의 find를 이용해 풀려고 했지만 n과 m이 100만으로 아주 크기 때문에
새로운 방법을 생각해야 한다.
문제에서 원하는 건 IOI, IOIOI, IOIOIOI.... 가 입력받은 문자열에 몇 번 들어가는지를 알아내는 것이다.
여기서 눈에 띄는 건 P(n)이 항상 IOI를 포함하고 있다는 것이고 n은 IOI가 몇 번 포함되었는지를 나타낸다.
따라서 IOI가 연속으로 몇 번 나왔는지를 체크하면 된다.
예를 들어, n이 3일 때 IOI가 연속으로 3번나왔다면 IOIOIOI가 문자열에 포함되었다는 뜻이 된다.
이를 구현한 코드는 다음과 같다.
4. 코드
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
string s;
cin >> n;
cin >> m;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
int k = 0;
if (s[i] == 'I')
{
while (s[i + 1] == 'O' && s[i + 2] == 'I')
{
k++;
if (n == k)
{
ans++;
k--;
}
i += 2;
}
}
}
cout << ans;
}
- 메시지? => WM_xxx, CB_xxx, LM_xxx, PBM_xxx 등으로 모두 양의 값
윈도우 프로시져가 메세지를 처리하는 코드는 다음과 같다.
//프로시져의 메시지 처리 방식
switch(message)
{
//각각의 메시지에 해당하는 처리
case 메시지1:
break;
case 메시지2:
break;
case 메시지3:
break;
//처리하지 않은 메시지에 대한 기본적인 처리
default:
DefWndProc();
}
#메시지 전달과 처리 과정
-메시지 루프와 WndProc()
while( GetMessage(&msg, NULL, 0, 0))
//메시지를 큐를 검사하면서 해당 응용프로그램의 메세지가 있는지 체크한다
{
TranslateMessage(&msg);//키보드 입력이 들어왔을때 어떤 문자가 눌렸는지 정보를 생성
DispatchMessage(&msg);//메세지를 윈도우 프로시져에게 보내주고
//윈도우 프로시져에게 처리되어 리턴된 값을 받아온다.
}
2. 프로젝트 생성, 문자집합
#멀티 바이트 문자 집합(MBCS)
- 1 ~ 2 Byte 크기의 문자 집합
(1 Byte로 표현할 수 없는 중국어, 일본어 등 지원)
- 영문과 한글 지원
- 일반 C함수는 MBCS 문자집합 사용
#유니코드 문자 집합
-2Byte로 전세계 언어를 표현하는 문자집합
-유니코드는 멀티바이트에 비해 메모리는
많이 차지하지만 처리속도는 더 빠름
-ASCII 코드 값의 일부는 유니코드와 같다. (문자, 숫자)
#문자 집합에 따른 데이터형 변환
-문자
TCHAR (ANSI,아스키) => CHAR(char)
TCHAR(Unicode) => WCHAR(wchar_t)
-문자열
LPTSTR(ANSI, 아스키) => LPSTR(char*)
LPTSTR(Unicode) => LPWSTR(wchar_t*)
-ANSI 문자열을 유니코드로 변환 매크로 함수, TEXT()
LPTSTR str = TEXT("문자열")
3. 윈도우 프로그래밍 기본 함수
#WinMain() 함수의 원형
#include<Windows.h>
#define WINAPI __stdcall
int WINAPI WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR IpCmdLine,
int nCmdShow){}
int APIENTRY _tWinMain() //Unicode 사용에 따라 달라지는 함수
{
ShowWindow(hWnd, nCmdShow);
//윈도우 출력
UpdateWindow(hWnd);
//윈도우 업데이트
//또는
ShowWindow(hWnd, SW_SHOW);
UpdateWindow(hWnd);
}
#WinMain() 작성 순서 5단계, 메시지 루프
{
//# 메시지 루프를 구성하는 함수
BOOL GetMessage(
LPMSG lpMsg,
HWND hWnd,
UINT wMsgFilterMin,
UINT wMsgFilterMax);
//GetMessage()
//메시지 큐에서 메시지를 가져오는 역할
//WM_QUIT(완전히 프로그램을 빠져나갈때)가 발생할 때만 FALSE 리턴
//그 외에는 TRUE 리턴
BOOL TranslateMessage(const MSG * lpMsg);
//문자 키 또는 키 입력에 대한 메시지 변환
//WM_KEYDOWN => WM_CHAR
LRESULT DispatchMessage(const MSG * lpMsg);
//WndProc() 함수 호출
//WndProc()가 종료될 때까지 대기
//WndProc()로 메시지 전달
//MSG 구조체
typedef struct {
HWND hwnd;
UINT message; //메세지
WPARAM wParam;//메시지와 함께 전달되는 정보
LPARAM lParam;//메시지와 함께 전달되는 정보
DWORD time;
POINT pt;
} MSG, *PMSG;
//메시지 루프 전체 구조
LPMSG msg;
while (GetMessage(&msg, NULL, 0, 0))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
5. WndProc() 작성
# WndProc() 기본 메세지
-WM_PAINT
:최초 UpdateWindow() 함수에 의해 발생,
윈도우의 일부 영역을 새로 출력할 때 발생
-WM_DESTROY
:윈도우가 화면에서 사라진 후에 보내지는 메시지,
메모리에서 제거되기 직전에 보내짐
# WndProc() 구성
LRESULT CALLBACK WndProc(HWND hWnd,
UINT message, WPARAM wParam,
LPARAM lParam)
{
PAINTSTRUCT ps;
HDC hdc;
switch (message)
{
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps); //화면 그리기 준비
EndPaint(hWnd, &ps); //화면 그리기 종료
break;
case WM_DESTROY:
//메모리 해제에 대한 코드가 들어가는 곳//
PostQuitMessage(0); //WM_QUIT 발생
break;
default:
return DefWindowProc(hWnd, message,
wParam, lParam);
return 0;
}
return 0;
6. 자동 생성 (VS 2022 버전)
// Windows API_AUTO.cpp : 애플리케이션에 대한 진입점을 정의합니다.
//
#include "framework.h"
#include "Windows API_AUTO.h"
#define MAX_LOADSTRING 100
// 전역 변수:
HINSTANCE hInst; // 현재 인스턴스입니다.
WCHAR szTitle[MAX_LOADSTRING]; // 제목 표시줄 텍스트입니다.
WCHAR szWindowClass[MAX_LOADSTRING]; // 기본 창 클래스 이름입니다.
// 이 코드 모듈에 포함된 함수의 선언을 전달합니다:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
int APIENTRY wWinMain(_In_ HINSTANCE hInstance,
_In_opt_ HINSTANCE hPrevInstance,
_In_ LPWSTR lpCmdLine,
_In_ int nCmdShow)
{
UNREFERENCED_PARAMETER(hPrevInstance);
UNREFERENCED_PARAMETER(lpCmdLine);
// TODO: 여기에 코드를 입력합니다.
// 전역 문자열을 초기화합니다.
LoadStringW(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadStringW(hInstance, IDC_WINDOWSAPIAUTO, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
// 애플리케이션 초기화를 수행합니다:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
HACCEL hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_WINDOWSAPIAUTO));
MSG msg;
// 기본 메시지 루프입니다:
while (GetMessage(&msg, nullptr, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
//
// 함수: MyRegisterClass()
//
// 용도: 창 클래스를 등록합니다.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEXW wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_WINDOWSAPIAUTO));
wcex.hCursor = LoadCursor(nullptr, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCEW(IDC_WINDOWSAPIAUTO);
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
return RegisterClassExW(&wcex);
}
//
// 함수: InitInstance(HINSTANCE, int)
//
// 용도: 인스턴스 핸들을 저장하고 주 창을 만듭니다.
//
// 주석:
//
// 이 함수를 통해 인스턴스 핸들을 전역 변수에 저장하고
// 주 프로그램 창을 만든 다음 표시합니다.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
hInst = hInstance; // 인스턴스 핸들을 전역 변수에 저장합니다.
HWND hWnd = CreateWindowW(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, nullptr, nullptr, hInstance, nullptr);
if (!hWnd)
{
return FALSE;
}
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
//
// 함수: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// 용도: 주 창의 메시지를 처리합니다.
//
// WM_COMMAND - 애플리케이션 메뉴를 처리합니다.
// WM_PAINT - 주 창을 그립니다.
// WM_DESTROY - 종료 메시지를 게시하고 반환합니다.
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_COMMAND:
{
int wmId = LOWORD(wParam);
// 메뉴 선택을 구문 분석합니다:
switch (wmId)
{
case IDM_ABOUT:
DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
}
break;
case WM_PAINT:
{
PAINTSTRUCT ps;
HDC hdc = BeginPaint(hWnd, &ps);
// TODO: 여기에 hdc를 사용하는 그리기 코드를 추가합니다...
EndPaint(hWnd, &ps);
}
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
// 정보 대화 상자의 메시지 처리기입니다.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
break;
}
return (INT_PTR)FALSE;
}
#MyRegisterClass()
: 윈도우 구조체 설정 및 등록
#InitInstance()
: 윈도우 생성 및 출력
#About()
: 정보 대화 상자의 메시지 처리기, 애플리케이션 정보 같은 것들 표시
# HACCEL hAccelTable;
: 단축기에 대한 것
# LoadString()
: 문자열을 리소스를 다루기 위해, 문자열에 대한 아이디를 부여하고, 프로그램을 쓸 때
아이디를 이용해 문자열을 해당 배열에 복사한다.
아이디가 부여된 문자열, 그리고 그에 대한 값
솔루션 탐색기/리소스 파일/rc파일/String Table
경로에 저장 되어 있다.
위의 모든 내용은
유튜브 아워즈팜X나우캠퍼스, "Win32 API 2강. Win32 API 프로그래밍 구조",
빈칸을 채울 때마다 조건 확인을 해주면 그 다음 재귀로 넘어가는 경우의 수는 많이 줄어든다.
4. 설명
빈칸에 1~9까지 수를 대입해보고
스도쿠 조건에 만족하지 않는다면 그 경우는 패스하고,
만족한다면 다음 빈칸으로 넘어간다.
만약 만족하는 수가 없다면 이전 선택이 잘못된 것이므로
이전의 빈칸으로 돌아간다.
빈칸이 모두 채워졌다면 종료한다.
5. 코드
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<tuple>
using namespace std;
const int INF = 0x7f7f7f7f;
typedef long long ll;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int board[10][10];
vector<pair<int,int>> zero;
bool Check(int x, int y, int num)
{
for (int i = 0; i < 9; i++)
{
if (board[i][y] == num) return false;
if (board[x][i] == num) return false;
}
//주변 9개 칸 중 같은 것이 있는지 확인
//*주의* C언어에서 x / 3 * 3 != x 이다.
// '/'연산은 나머지를 날려버리기 때문이다.
for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
{
for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
{
if (board[i][j] == num) return false;
}
}
return true;
}
int ans[10][10];
void solve(int cur)
{
//빈 칸을 다 채웠을 시 종료
if (cur == zero.size())
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) ans[i][j] = board[i][j];
return;
}
int cx, cy;
tie(cx, cy) = zero[cur];
//적절한 수인지 확인 후 다음 빈칸으로 넘어간다
for (int i = 1; i <= 9; i++)
{
if (Check(cx, cy, i))
{
board[cx][cy] = i;
solve(cur + 1);
board[cx][cy] = 0;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cin >> board[i][j];
if (board[i][j] == 0) zero.push_back({ i, j });
}
}
solve(0);
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++) cout << ans[i][j] << ' ';
cout << '\n';
}
}
