개발 블로그

문제 링크 : www.acmicpc.net/problem/1952

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

접근 방법

시작 지점 [0][0]에서 시작해서 오, 아, 왼, 위 방향 순으로 전진하며, 

이미 map[nr][nc]가 1이거나(방문 먼저 했거나) 범위 넘어가면 카운트를 증가한다.

M*N 만큼 칸을 방문하면 반복문을 멈춘다.

//
//  SM_BOJ1952_달팽이2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01. 4:46 ~ 
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string.h>
using namespace std;

int map[101][101];
//오 아 왼 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

int main(){
    
    int M, N;
    cin >> M >> N;
    
    memset(map, 0, sizeof(map));
    int ans = 0;
    int cnt = 1;
    
    int d= 0;
    int r = 0;
    int c = 0;
    map[r][c] = 1;
    while(1){
        
        if(cnt== M*N) break;
          
        int nr = r + dr[d];
        int nc = c + dc[d];
        
        //범위 넘어가거나 이미 map[i][j]==1 이면
        if(nr<0 || nr>M-1 || nc<0 || nc>N-1 || map[nr][nc]==1){
            ans += 1;
            if(d==3) d = 0;
            else d = d+1;
        }
        else{
            map[nr][nc] = 1;
            cnt += 1;
            r = nr;
            c = nc;
        }
    }
    cout << ans; 
    
    
    
    return 0;
}